震惊！99%的人都会做的题目，某ZZOIer竟然DEBUG了半天！点击查看->：BZOJ 4379 Modernizacja autostrady

发表于 | 更新于

Link

总算能基本上自己做出来一道题目了虽然是水题

Solution

可以发现，把一棵树从一条边剖开，要合起来最长的直径就是两个子树的直径和 最短的直径就是把两个直径的中点相连。所以主要问题就是快速算直径 设从pospos到fa[pos]fa[pos]的连边把树剖开，pospos的子树中的直径可以预处理，那么另一部分直径有这样几个来源：

  1. fa[pos]fa[pos]祖先们除了fa[pos]fa[pos]所在子树之外的子树中的直径
  2. fa[pos]fa[pos]的子树刨去pospos的子树剩下部分的直径
  3. fa[pos]fa[pos]下面连一条长链，向上伸到一个祖先，再向下连一条长链

观察之后，发现一遍预处理，对于以pp为根的子树，处理出pp子树的直径，pp的子节点的子树的直径的最大、次大值，和从pp向下的前三长的链，就可以做前两个。 第三个只需要在DP的时候在栈上记录一个从祖先来的最长链即可 大体就是这样 写了一个来小时，然后开启了DEBUG被坑模式

Tips

改来改去，其实主要就改了3个错误，而3个错误的外观是一样的：输出方案里有0。 具体地说，是使得直径最小的连边出现了0。

  1. 我在DP的时候记录了每个链的一个端点，输出方案的时候需要找到直径的中点，那就再从端点开始DFS一下就好了。然后一开始我把两个直径的端点设置成了不可访问，导致第一个的DFS几乎搜遍了整个树，把第二遍DFS需要找的点也给搜了！！
  2. 然后我找到了问题，设置成了两个断点不可用，再从端点开始搜，还是出来0。最后发现，把断点设置不可用，直接把一些合法的链截断了！！！！
  3. 然后我找到了问题，设置了每遍DFS都是另一个断点不可用，还是出来0。最后发现，我的DP中因为存在一些 ，我盲目地和00取了max\max，导致一些不存在的状态被合法化了！！！
  4. 然后几乎3h就过去了。

通过做这道题题目使我充分认识到自己能犯的错误有多么SX。 所以，至少要总结这几点经验： 想想遍历之前设置不可用的点截断的是什么 DP，尤其是记录方案的DP，即使是0这样的值也一定要有来由！

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include "lucida"

using std::pair;
using std::make_pair;
using std::max;
template <class T>
inline T max(const T &a,const T &b,const T &c) {
	return max(a,max(b,c));
}
const int MAXN=500000+11,INF=0x1f1f1f1f;
struct Edge {
	int to,v;
	Edge *pre;
	Edge(int to,int v,Edge *pre):to(to),v(v),pre(pre){}
	void *operator new(size_t);
}*id[MAXN];
void *Edge::operator new(size_t) {
	static Edge *Pool=(Edge*)malloc((MAXN<<1)*sizeof(Edge)),*Me=Pool;
	return Me++;
}
void Adde(int f,int t) {
	id[f]=new Edge(t,1,id[f]);
	id[t]=new Edge(f,1,id[t]);
}
struct Node {
	int v,end;
	Node(){v=-INF;} Node(int v,int end):v(v),end(end){}
	bool operator <(const Node &a) const {
		return v<a.v;
	}
};
template <int d> struct FST {
	Node v[d];
	Node &operator [](int x){
		return v[x];
	}
	void Append(const Node &p) {
		for(int i=0;i<d;++i) 
			if(v[i].v<p.v) {
				for(int j=d-1;j>i;--j)
					v[j]=v[j-1];
				v[i]=p;
				break;
			}
	}
};///;;;;;!!
FST<3> ch[MAXN];
FST<2> sond[MAXN];
Node d[MAXN];
int fa[MAXN],lbd[MAXN],rbd[MAXN],dc;
void Calc(int pos) {
	bool isleaf=1;
	lbd[pos]=++dc;
	for(Edge *e=id[pos];e;e=e->pre) 
		if(e->to!=fa[pos]) {
			int u=e->to;
			isleaf=0;
			fa[u]=pos;
			Calc(u);
			ch[pos].Append(Node(ch[u][0].v+1,ch[u][0].end));
			sond[pos].Append(d[u]);
		}
	if(isleaf) 
		ch[pos][0]=d[pos]=Node(0,pos);
	else 
		d[pos]=max(Node(ch[pos][0].v+max(ch[pos][1].v,0),ch[pos][0].end),sond[pos][0]);
	rbd[pos]=dc;
	
}
Node O_O(int pos,Node parch) {
	int f=fa[pos];
	Node r1,r2=Node(0,f),fsd=(sond[f][0].end!=d[pos].end?sond[f][0]:sond[f][1]),fd=Node(0,f);
	if(ch[f][0].end==ch[pos][0].end) {
		chkmx(fd,Node(ch[f][1].v+max(ch[f][2].v,0),ch[f][1].end));//出现了end为0的不合法
		chkmx(r2,Node(max(ch[f][1].v,0)+parch.v+1,parch.end));
	} else if(ch[f][1].end==ch[pos][0].end) {
		chkmx(fd,Node(ch[f][0].v+max(ch[f][2].v,0),ch[f][0].end));
		chkmx(r2,Node(max(ch[f][0].v,0)+parch.v+1,parch.end));
	} else {
		chkmx(fd,Node(ch[f][0].v+max(ch[f][1].v,0),ch[f][0].end));
		chkmx(r2,Node(max(ch[f][0].v,0)+parch.v+1,parch.end));
	}
	r1=max(Node(0,f),fd,fsd);
	return max(r1,r2);
}
pair<int,int> cut[2],lnk[2];
int Ans[2]={INF,-INF};
//d2：父节点(不包含)以上的部分的直径
//fch：包含父节点的最长链
//DFF：父节点子树之内剩下的部分的直径
//DGF: 父节点的子树之内的一条长链和上面过来的长链构成的长度
//O_O：max(DGF,DFF) 即父节点带来的最长链
//parch 祖先到父节点(不包含)的最长链 也就是到爷节点为止的最长链
pair<int,int> dist;
void DP(int pos,Node d2,Node parch) {
	if(pos!=1) {
		if(fa[pos]!=1)
			chkmx(parch.v,0);
		Node d1=d[pos];
		chkmx(d2,O_O(pos,parch));
		if(chkmn(Ans[0],max(d1.v,d2.v,d1.v-(d1.v>>1)+d2.v-(d2.v>>1)+1))) {
			cut[0]=make_pair(pos,fa[pos]);
			lnk[0]=make_pair(d1.end,d2.end);
			dist=make_pair(d1.v,d2.v);
		}
		if(chkmx(Ans[1],d1.v+d2.v+1)) {
			cut[1]=make_pair(pos,fa[pos]);
			lnk[1]=make_pair(d1.end,d2.end);
		}
		parch.v++;
		chkmx(parch,ch[fa[pos]][0].end!=ch[pos][0].end?ch[fa[pos]][0]:ch[fa[pos]][1]);
		
	}
	for(Edge *e=id[pos];e;e=e->pre)
		if(e->to!=fa[pos]) {
			int u=e->to;
			DP(u,d2,parch);
		}
}
bool ud[MAXN];
int stack[MAXN],top;
int DFS(int pos,int d) {
	stack[++top]=pos;
	if(top==d+1)
		return stack[top-(top>>1)];//(d+1)>>1];
	for(Edge *e=id[pos];e;e=e->pre) 
		if(!ud[e->to]) {
			int u=e->to;
			ud[u]=1;
			int res=DFS(u,d);
			if(res)
				return res;
		}
	top--;
	return 0;
}
int main() {
//	freopen("input","r",stdin);
	int n;is>>n;
	for(int i=1;i<=n-1;++i) {
		int u,v;
		is>>u>>v;
		Adde(u,v);
	}
	Calc(1);
	DP(1,Node(-INF,0),Node(-INF,1));
	ud[cut[0].first]=1;
	top=0;
	ud[cut[0].second]=1;
	ud[cut[0].first]=0;
	lnk[0].first=DFS(lnk[0].first,dist.first);
	top=0;
	ud[cut[0].first]=1;
	ud[cut[0].second]=0;
	lnk[0].second=DFS(lnk[0].second,dist.second);
	
	for(int d=0;d<=1;++d)
		os<<Ans[d]<<' '<<cut[d].first<<' '<<cut[d].second<<' '<<lnk[d].first<<' '<<lnk[d].second<<'\n';
	return 0;
}