通道[WC2018]

发表于 分类于 ，

题目链接

链接

题意

三棵树，求 $d_1(i,j)+d_2(i,j)+d_3(i,j)$ 的最大值。其中 $d$ 表示距离。

$n\leq 10^5$

题解

似乎有乱搞做法。。不管了。

一棵树

是个OIer都会。

两棵树

$d(i,j)$ 可以表示为 $dis_i+dis_j-2\times dis_{lca(i,j)}$，其中 $dis_i$ 表示点 $i$ 到根节点的距离。

考虑枚举 $T_1$ 中的 $lca$，那么 $i,j$ 需要从以 $lca$ 为根的子树中选出来，且不能是同一棵子树，或者有一个是 $lca$。

类似于树形DP，考虑每次将一个子树添加进去，然后维护答案。

这时答案为：$dis_i+dis_j+d_2(i,j)-2\times dis_{lca}$。后面是个常数，我们只需要维护前面的最大值。

考虑树的直径的一个重要性质，若记集合中任意两个最远的点为 $u,v$，那么对于两个集合 $A,B$，$A\bigcup B$ 的 $u,v$ 一定出自于 $A_u,A_v,B_u,B_v$ 中的任意两个。证明的话可以先证明连通的情况，不连通情况的建个虚树。

那么如果没有 $dis_i$ 和 $dis_j$，$d_2(i,j)$ 的最大值用个结构体维护一下就好了。

可以看做在 $T_2$ 中，新建一个点 $i’$，由 $i$ 和 $i’$ 连一条权值为 $dis_i$ 的边，这样就变成树的直径了。因此加上 $dis_i+dis_j$ 也是正确的。

时间复杂度 $O(n)$。

以我的水平就只能想到这里了。

三棵树

对 $T_3$ 考虑分治。

然而点分治合并两个子树信息的时候不一定搞得了。

然后就考虑边分治。。。

枚举一条边 $i$，将树拆成两部分，然后黑白染色。黑白两部分间的贡献递归去算。

那么题目转换成黑白两集合各选一个点 $x,y$，那么这棵树的贡献就是 $d_1x+d_1y-val_i$。

看看 $T_1,T_2$ 能不能沿用前面的方法。

但是现在多了一个 $d1$，还有黑白的颜色，以及能不能选上这个点的限制条件。

考虑设 $w_x=d_1x+d_2x$，那么 $T_2$ 中的贡献则变为 $w_x+w_y-2\times d_2lca$。

而黑白集合还是可以一样的维护。即用 $f_{u,0/1}$ 表示两个集合的直径。

但是一次dp是 $O(n)$ 的。

那么建个虚树就好了。

还有一个问题，边分治在菊花图的时候会死得很惨。

此时需要用到多叉树转二叉树，并且不能改变距离的限制，因此不能用左二子右兄弟法。

对于每个度数大于2（除父亲节点）的节点 $i$，添加两个点 $l,r$，连边 $(i,l/r,0)$，然后将子节点分成一半连向 $l,r$，然后再处理 $l,r$ 即可。

这样复杂度就能有保证了。

因此我们需要：

  • 将 $T_1$ 转成二叉树，然后边分治。
  • 在 $T_2$ 中建虚树，然后枚举虚树中的点作为 $lca$ ，然后将子树信息 $O(1)$ 合并。建虚树求LCA需要用 $O(n\log n)-O(1)$ 的ST表做法。
  • 在 $T_3$ 中用 $O(n\log n)-O(1)$ 的ST表做法快速求LCA即可。

若用 $O(n)$ 时间建虚树，时间复杂度 $O(n\log n)$。

程序

写了我一个上午…

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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cout<<#x<<"="<<x<<endl;
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline ll read()
{
	ll x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
const int N=600010;
const int M=18;
const int inf=2e9;
const ll Inf=4e18;
int lg[N];
namespace T3{
	int ne[N],head[N],ver[N],tot=1,dep[N];
	ll val[N],dis[N];
	int cnt,fir[N],f[M][N/3];
	inline void add(ll z,int y,int x)
	{
		ver[++tot]=y; val[tot]=z; ne[tot]=head[x]; head[x]=tot;
		ver[++tot]=x; val[tot]=z; ne[tot]=head[y]; head[y]=tot;
	}
	void dfs(int u,int pre)
	{
		dep[u]=dep[pre]+1; f[0][++cnt]=u; fir[u]=cnt;
		for(int i=head[u],v;i;i=ne[i])
			if((v=ver[i])!=pre)
			{
				dis[v]=dis[u]+val[i];
				dfs(v,u);
				f[0][++cnt]=u;
			}
	}
	inline int cmp(int x,int y){return dep[x]<dep[y]?x:y;}
	void pre()
	{
		dfs(1,0);
		fo(j,1,M-1)
			fo(i,1,cnt+1-(1<<j))
				f[j][i]=cmp(f[j-1][i],f[j-1][i+(1<<(j-1))]);
	}
	inline int lca(int x,int y)
	{
		x=fir[x]; y=fir[y];
		if(x>y) swap(x,y);
		int k=lg[y-x+1];
		return cmp(f[k][x],f[k][y-(1<<k)+1]);
	}
	inline ll d(int x,int y){if(!x||!y) return -Inf; return dis[x]+dis[y]-(dis[lca(x,y)]<<1);}
}
int top[2],s[2][N];
ll w[2][N];
namespace T2{
	ll ans;
	int ne[N],head[N],ver[N],tot=1,dep[N];
	int dfn[N],tim,low[N];
	ll val[N],dis[N];
	int cnt,fir[N],f[M][N/3];
	inline void add(ll z,int y,int x)
	{
		ver[++tot]=y; val[tot]=z; ne[tot]=head[x]; head[x]=tot;
		ver[++tot]=x; val[tot]=z; ne[tot]=head[y]; head[y]=tot;
	}
	inline void _add(int x,int y,ll z)
	{
		ver[++tot]=y; val[tot]=z; ne[tot]=head[x]; head[x]=tot;
	}
	void dfs(int u,int pre)
	{
		dep[u]=dep[pre]+1; f[0][++cnt]=u; fir[u]=cnt;
		dfn[u]=++tim;
		for(int i=head[u],v;i;i=ne[i])
			if((v=ver[i])!=pre)
			{
				dis[v]=dis[u]+val[i];
				dfs(v,u);
				f[0][++cnt]=u;
			}
		low[u]=tim;
	}
	inline int cmp(int x,int y){return dep[x]<dep[y]?x:y;}
	void pre()
	{
		dfs(1,0);
		fo(j,1,M-1)
			fo(i,1,cnt+1-(1<<j))
				f[j][i]=cmp(f[j-1][i],f[j-1][i+(1<<(j-1))]);
		memset(head,0,sizeof(head));
		tot=1;
	}
	inline int lca(int x,int y)
	{
		x=fir[x]; y=fir[y];
		if(x>y) swap(x,y);
		int k=lg[y-x+1];
		return cmp(f[k][x],f[k][y-(1<<k)+1]);
	}
	int b[N],m,opt[N],st[N];
	ll va[N];
	bool vis[N];
	struct node{
		int u,v;
		ll dis;
		friend inline bool operator<(const node &A,const node &B)
		{
			if(!A.u) return 1;
			if(!B.u) return 0;
			return A.dis<B.dis;
		}
	};
	inline node make_node(int u,int v,ll d)
	{
		return (node){min(u,v),max(u,v),d};
	}
	inline node make_node(int u,int v)
	{
		return (node){min(u,v),max(u,v),T3::d(u,v)+va[u]+va[v]};
	}
	inline node merge(const node &A,const node &B)
	{
		node ans=max(A,B);
		ans=max(ans,max(max(make_node(A.u,B.u),make_node(A.u,B.v)),max(make_node(A.v,B.u),make_node(A.v,B.v))));
		return ans;
	}
	inline ll diameter(const node &A,const node &B)
	{
		if(!A.u&&!A.v) return -Inf; if(!B.u&&!B.v) return -Inf;
		return max(max(make_node(A.u,B.u),make_node(A.u,B.v)),max(make_node(A.v,B.u),make_node(A.v,B.v))).dis;
	}
	node dp[N][2];
	void dfs(int u)
	{
		dp[u][0]=dp[u][1]=(node){0,0,0};
		if(vis[u]) dp[u][opt[u]]=(node){u,u,0};
		for(int i=head[u],v;i;i=ne[i])
		{
			v=ver[i];
			dfs(v);
			ans=max(ans,max(diameter(dp[u][0],dp[v][1]),diameter(dp[u][1],dp[v][0]))-dis[u]*2);
			dp[u][0]=merge(dp[u][0],dp[v][0]);
			dp[u][1]=merge(dp[u][1],dp[v][1]);
		}
	}
	inline void build_tree()
	{
		m=0;
		fo(j,0,1) fo(i,1,top[j]) b[++m]=s[j][i];
		sort(b+1,b+m+1,[&](const int &x,const int &y){return dfn[x]<dfn[y];});
		fo(i,1,m) vis[b[i]]=1;
		fo(j,0,1) fo(i,1,top[j]) opt[s[j][i]]=j;
		fo(j,0,1) fo(i,1,top[j]) va[s[j][i]]=w[j][i]+dis[s[j][i]];
		fo(i,1,m-1) b[++m]=lca(b[i],b[i+1]);
		sort(b+1,b+m+1,[&](const int &x,const int &y){return dfn[x]<dfn[y];});
		m=unique(b+1,b+m+1)-b-1;
		fo(i,1,m) head[b[i]]=0; tot=1;
		int top=0;
		fo(i,1,m)
		{
			for(;top&&low[st[top]]<dfn[b[i]];--top);
			if(top) _add(st[top],b[i],dis[b[i]]-dis[st[top]]);
			st[++top]=b[i];
		}
	}
	void init()
	{
		fo(i,1,m) va[b[i]]=opt[b[i]]=vis[b[i]]=head[b[i]]=0;
		m=0; tot=1;
	}
	inline ll solve()
	{
		ans=0;
		build_tree();
		ans=0;
		dfs(b[1]);
		init();
		return ans;
	}
}
int n;
namespace T1{
	int pre_n;
	int ne[N],head[N],ver[N],tot=1;
	ll val[N];
	bool vis[N];
	inline void add(int x,int y,ll z)
	{
		ver[++tot]=y; val[tot]=z; ne[tot]=head[x]; head[x]=tot;
		ver[++tot]=x; val[tot]=z; ne[tot]=head[y]; head[y]=tot;
	}
	vector<int> son[N]; ll value[N];
	void dfs(int u,int pre)
	{
		for(int i=head[u],v;i;i=ne[i])
			if((v=ver[i])!=pre)
			{
				dfs(v,u);
				son[u].pb(v); value[v]=val[i];
			}
	}
	void rebuild()
	{
		dfs(1,0);
		fo(i,1,n) head[i]=0;
		tot=1;
		int N=n,w[2],d=0;
		for(int i=1;i<=N;i++)
			if(son[i].size()<=2) for(auto v:son[i]) add(i,v,value[v]);
			else
			{
				w[0]=++N; w[1]=++N;
				add(i,w[0],0); add(i,w[1],0);
				for(auto v:son[i])
				{
					d=1-d; son[w[d]].pb(v);
				}
			}
		n=N;
	}
	int siz[N],minn,edge;
	ll dis[N];
	void getroot(int u,int pre,int s)
	{
		siz[u]=1;
		for(int i=head[u],v,tmp;i;i=ne[i])
			if((v=ver[i])!=pre&&!vis[i>>1])
			{
				getroot(v,u,s);
				siz[u]+=siz[v];
				tmp=max(siz[v],s-siz[v]);
				if(tmp<minn) minn=tmp,edge=i;
			}
	}
	int now;
	void getdis(int u,int pre)
	{
		if(u<=pre_n)
		{
			++top[now];
			s[now][top[now]]=u;
			w[now][top[now]]=dis[u];
		}
		for(int i=head[u],v;i;i=ne[i])
			if(!vis[i>>1]&&(v=ver[i])!=pre)
			{
				dis[v]=dis[u]+val[i];
				getdis(v,u);
			}
	}
	ll ans;
	void divide(int u,int s)
	{
		minn=inf; getroot(u,0,s);
		if(minn>=inf) return;
		int j=edge,s1=siz[ver[j]],s2=s-s1;
		vis[j>>1]=1; top[0]=top[1]=0;
		dis[ver[j]]=dis[ver[j^1]]=0;
		now=0; getdis(ver[j],0);
		now=1; getdis(ver[j^1],0);
		ll tmp=val[j]+T2::solve();
		ans=max(ans,tmp);
		fo(j,0,1) fo(i,1,top[j]) w[j][i]=0;
		divide(ver[j],s1); divide(ver[j^1],s2);
	}
	inline void work()
	{
		pre_n=n;
		rebuild();
		ans=0;
		divide(1,n);
		printf("%lld\n",ans);
	}
}
int main()
{
	n=read();
	fo(i,2,n<<1) lg[i]=lg[i>>1]+1;
	int x,y; ll z;
	fo(i,2,n) x=read(),y=read(),z=read(),T1::add(x,y,z);
	fo(i,2,n) T2::add(read(),read(),read());
	fo(i,2,n) T3::add(read(),read(),read());
	T3::pre(); T2::pre(); T1::work();
	return 0;
}