CTSC2018 暴力写挂

发表于
字数统计: 2,284字 | 阅读时长 ≈ 11min

「CTSC2018」暴力写挂

题目描述

temporaryDO 是一个很菜的 OIer 。在 4 月，他在省队选拔赛的考场上见到了《林克卡特树》一题，其中 $k = 0$ 的部分分是求树 $T$ 上的最长链。可怜的 temporaryDO 并不会做这道题，他在考场上抓猫耳挠猫腮都想不出一点思路。
这时，善良的板板出现在了空中，他的身上发出璀璨却柔和的光芒，荡漾在考场上。‘‘题目并不难。’’ 板板说。那充满磁性的声音，让 temporaryDO 全身充满了力量。
他决定：写一个枚举点对求 LCA 算距离的 $k = 0$ 的 $O(n^2\ log\ n)$ 的部分分程序！于是， temporaryDO 选择以 $1$ 为根，建立了求 LCA 的树链剖分结构，然后写了二重 for 循环枚举点对。
然而，菜菜的 temporaryDO 不小心开小了数组，于是数组越界到了一片神秘的内存区域。但恰好的是，那片内存区域存储的区域恰好是另一棵树 $T′$ 。这样一来，程序并没有 RE ，但他求 $x$ 和 $y$ 的距离的时候，计算的是

最后程序会输出每一对点对 $i, j (i \le j)$ 的如上定义的‘‘距离’’ 的最大值。
temporaryDO 的程序在评测时光荣地爆零了。但他并不服气，他决定花好几天把自己的程序跑出来。请你根据 $T$ 和 $T′$ 帮帮可怜的 temporaryDO 求出他程序的输出。

输入格式

第一行包含一个整数 $n$ ，表示树上的节点个数；
第 $2$ 到第 $n$ 行，每行三个整数 $x , y , v$ ，表示 $T$ 中存在一条从 $x$ 到 $y$ 的边，其长度为 $v$ ；
第 $n + 1$ 到第 $2n - 1 行$ ，每行三个整数 $x , y , v$ ，表示 $T′$ 中存在一条从 $x$ 到 $y$ 的边，其长度为 $v$ 。

输出格式

输出一行一个整数，表示 temporaryDO 的程序的输出。

数据范围与提示

对于所有数据， $n \le 366666 , |v| \le 2017011328$ 。
详细数据范围见下表，表格中的‘‘无’’ 表示无特殊限制。

测试点编号 $n \le$ $v$ $T$ 是一条链 $T’$ 是一条链
1 36 $=1$ 否 否
2 366 $=1$ 否 否
3 1388 $>0$ 否 否
4 1999 $>0$ 否 否
5 2666 $>0$ 否 否
6 5666 无 否 否
7 8666 无 否 否
8 11111 无 否 否
9 12345 无 否 否
10 366666 $>0$ 是 是
11 366666 无 是 是
12~13 366666 $>0$ 是 否
14 366666 无 是 否
15~16 366666 $>0$ 否 是
17 366666 无 否 是
18~20 366666 无 否 否

$depth(p)$ 和 $depth′(p)$ 分别表示树 $T$ 、 $T′$ 中点 $1$ 到点 $p$ 的距离，这里规定，距离指的是经过的边的边权总和，其中 $depth(1) = 0$ 。
$LCA(x, y)$ 和 $LCA′(x, y)$ 分别表示树 $T$ 、 $T′$ 中点 $x$ 与点 $y$ 的最近公共祖先，即在从 $x$ 到 $y$ 的最短路径上的距离根经过边数最少的点。

据出题人说点分治比较难写，而且复杂度不太对……但是并不知道点分治怎么搞。

首先说说大体思路：考虑使用对$T$使用边分治，每次枚举分别位于重心边两边的点对$x,y$，维护出$dep(x)+dep(y)-dep(LCA(x,y))$，建出$T’$对应的虚树,在建树的过程中更新答案。

具体来说，发现前一部分是这样的三段之和：$x->LCA,y->LCA,LCA->root$。不妨把它拆成两部分：$x->root,y->LCA$。注意这里的$root$是原树$T$的根。下面维护分治中心的子树中，节点到$root$的距离$f[x][1]$，维护剩下部分的节点到“分治中心$->root$”这条链的距离$f[y][0]$。容易发现$f[x][1]+f[y][0]$就是这两部分的和。

考虑建虚树的过程。为了得到所有点对的答案，只需要在弹栈的同时更新答案，并且用弹出元素的$f[x][0],f[x][1]$更新当前栈顶元素的$f[x][0],f[x][1]$即可，这样做相当于是在两点的$LCA’$处讨论到了它们（之前讨论到的那个点的$f[x][0],f[x][1]$产生的贡献已经更新到了$’LCA$中）。

具体实现还有很多细节，详见代码。（%%%spj大神，这道题基本上就靠学习他的代码了）

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
#include<stdio.h>
#include<algorithm>
#include<cstring>
#define ll long long
#define MAXN 800005
#define MAXM 1600005
using namespace std;
const ll inf=(1ll<<60);

char *p1,*p2,buf[1<<20];
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline ll _R(){
	char s=GC;ll v=0;int sign=0;
	while((s!='-')&&(s>57||s<48))s=GC;
	if(s=='-')sign=1,s=GC;
	for(;s>47&&s<58;s=GC)v=v*10+s-48;
	return sign?-v:v;
}

int N;
ll Ans=-inf;

struct Tree{

int totn;
ll dep[MAXN];
int In[MAXN],Out[MAXN],Id[MAXN],fa[MAXN],Vt;
int en[MAXM],nex[MAXM],las[MAXN],tot;ll len[MAXM];

void add(int x,int y,ll z){
	en[++tot]=y;
	nex[tot]=las[x];
	las[x]=tot;
	len[tot]=z;
}

void link(int x,int y,ll z){
	add(x,y,z);add(y,x,z);
}

void del(int x,int y){
	int i=las[x],pre;
	if(en[i]==y){las[x]=nex[i];return;}
	for(pre=i,i=nex[i];i;pre=i,i=nex[i])if(en[i]==y){
		nex[pre]=nex[i];
		return;
	}
}

void build(int x,int f,Tree &T){//边分治建树
	int i,y,o=x,flag=0;
	for(i=las[x];i;i=nex[i]){
		y=en[i];if(y==f)continue;
		if(flag){
			T.totn++;
			T.link(x,T.totn,0);
			x=T.totn;
		}
		T.link(x,y,len[i]);
		build(y,o,T);
		flag=1;
	}
}

void rebuild(Tree &T){
	T.totn=N;
	build(1,0,T);
}

void dfs(int x,int f){
	int i,y;
	In[x]=++Vt;Id[Vt]=x;fa[x]=f;
	for(i=las[x];i;i=nex[i]){
		y=en[i];if(y==f)continue;
		dep[y]=dep[x]+len[i];
		dfs(y,x);
	}
	Out[x]=Vt;
}

int LCA(int x,int y){
	while(x!=y){
		if(In[x]<In[y])y=fa[y];
		else x=fa[x];
	}
	return x;
}//求dfs序相邻的lca,暴力搞好像是均摊O(1)的？

}Tmp,T1,T2;

int fa[MAXN],sz[MAXN];
int lca[MAXN],list[MAXN],tlca[MAXN],tlist[MAXN];
int Q[MAXN],hd,tl;
int S[MAXN],tp;ll f[MAXN][2];

void update(int x,int y){//x在虚树上是y的父亲，用y更新x
	Ans=max(Ans,max(f[x][0]+f[y][1],f[x][1]+f[y][0])-T2.dep[x]);
	f[x][0]=max(f[x][0],f[y][0]);
	f[x][1]=max(f[x][1],f[y][1]);
}

void DC(int rt,int l,int r){
	if(l>r)return;
	if(l==r){
		Ans=max(Ans,T1.dep[list[l]]-T2.dep[list[l]]);
		return;
	}
	
	int mid;
	
	int i,x,y,in,out;
	
	hd=1;tl=0;
	Q[++tl]=rt;fa[rt]=0;
	
	while(hd<=tl){
		x=Q[hd];sz[x]=1;
		for(i=T1.las[x];i;i=T1.nex[i]){
			y=T1.en[i];if(y==fa[x])continue;
			fa[y]=x;Q[++tl]=y;
		}
		hd++;
	}
	
	int mn=1e9,mx;
	
	for(i=tl;i;i--)if(fa[Q[i]])sz[fa[Q[i]]]+=sz[Q[i]];
 	for(i=tl;i;i--){
   		mx=max(sz[rt]-sz[Q[i]],sz[Q[i]]);
		if(mx<mn)mn=mx,mid=Q[i];
	}
    //上面是用bfs存了一下需要讨论的节点，同时找到重心边<mid,fa[mid]>
    
	tp=0;S[++tp]=list[l];
	for(i=l;i<r;i++)f[lca[i]][0]=f[lca[i]][1]=-inf;//注意由于要在LCA处更新答案，所以要处理一下
	
	for(i=1;i<=tl;i++){
		x=Q[i];
		in=T1.In[x];out=T1.Out[x];
		if(in>T1.Out[mid]||in<T1.In[mid]){
			if(T1.In[mid]<=out&&in<=T1.In[mid])f[x][1]=-inf,f[x][0]=0;//x在分治中心->root的链上
			else f[x][1]=-inf,f[x][0]=f[fa[x]][0]+T1.dep[x]-T1.dep[fa[x]];
		}
		else f[x][0]=-inf,f[x][1]=T1.dep[x];
	}
	
	tp=0;S[++tp]=list[l];
	
	for(i=l+1;i<=r;i++){
		x=list[i];y=lca[i-1];
		while(tp>1&&T2.In[S[tp-1]]>=T2.In[y]){
			update(S[tp-1],S[tp]);
			tp--;
		}
		if(S[tp]==y)S[++tp]=x;
		else{
			update(y,S[tp]);
			S[tp]=y;
			S[++tp]=x;
		}
	}
	while(tp>1)update(S[tp-1],S[tp]),tp--;
	//上面是建虚树+更新答案
	int tmp,t=0;
	
	for(i=l;i<=r;i++){
		in=T1.In[list[i]];
		if(in>=T1.In[mid]&&in<=T1.Out[mid])tlist[++t]=tlca[t]=list[i];
		if(t&&T2.In[tlca[t]]>T2.In[lca[i]])tlca[t]=lca[i];
	}
	tmp=t;
	for(i=l;i<=r;i++){
		in=T1.In[list[i]];
		if(in<T1.In[mid]||in>T1.Out[mid])tlist[++t]=tlca[t]=list[i];
		if(t&&T2.In[tlca[t]]>T2.In[lca[i]])tlca[t]=lca[i];
	}
	//处理虚树的lca
    
	for(i=0;i<=r-l;i++)lca[i+l]=tlca[i+1],list[i+l]=tlist[i+1];
	if(fa[mid])T1.del(mid,fa[mid]),T1.del(fa[mid],mid);

	DC(mid,l,l+tmp-1);DC(rt,l+tmp,r);
}

int main(){
	int i,x,y;ll z;
	N=_R();
	for(i=1;i<N;i++){
		x=_R();y=_R();z=_R();
		Tmp.link(x,y,z);
	}
	
	Tmp.rebuild(T1);
	
	for(i=1;i<N;i++){
		x=_R();y=_R();z=_R();
		T2.link(x,y,z);
	}
	
	T1.dfs(1,0);
	T2.dfs(1,0);
	for(i=1;i<=N;i++){
		if(i!=N)lca[i]=T2.LCA(T2.Id[i],T2.Id[i+1]);
		list[i]=T2.Id[i];
	}
	
	DC(1,1,N);
	
	printf("%lld\n",Ans);
}