边分治模板题
（第一次写边分治就记一下吧）
对式子变形，即为$\frac{dep_{x}+dep_{y}+dis(x,y)}{2}-dep'_{lca'(x,y)}$
通过增加节点使每一个点的度数都不超过3，不难证明此时总存在一条边，假设其将其删除后两连通块大小分别为$x$和$y$，则有$y\le 2x+1$且$x\le 2y+1$
由此，每次找到一条满足此条件的边并拆分，显然层数为$o(\log n)$，每一层将（到对应连通块根的）距离加入深度并在第二课树上建立虚树，然后lca为某点的最大新深度和即可
时间复杂度为$o(n\log^{2}n)$，可以通过
当然如果将虚树（排序和求lca）做到线性，复杂度即可做到$o(n\log n)$，但意义不大
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define N 400005
4 #define ll long long
5 #define vi vector<int>
6 #define fi first
7 #define se second
8 struct Edge{
9 int nex,to,len;
10 };
11 int n;
12 ll ans,val[N];
13 ll calc(vi x,vi y);
14 namespace T1{
15 int m,E,rt,x,y,z,head[N<<1],sz[N<<1],vis[N<<1];
16 ll dep[N<<1];
17 vi v,vx,vy;
18 vector<pair<int,int> >e[N<<1];
19 Edge edge[N<<2];
20 void add(int x,int y,int z){
21 edge[E]=Edge{head[x],y,z};
22 head[x]=E++;
23 }
24 void dfs(int k,int fa,ll s){
25 dep[k]=s;
26 for(int i=head[k];i!=-1;i=edge[i].nex)
27 if (edge[i].to!=fa)dfs(edge[i].to,k,s+edge[i].len);
28 v.clear();
29 for(int i=head[k];i!=-1;i=edge[i].nex)
30 if (edge[i].to!=fa)v.push_back(edge[i].to);
31 int lst=k;
32 for(int i=0;i+2<v.size();i++){
33 e[lst].push_back(make_pair(v[i],dep[v[i]]-dep[k]));
34 e[lst].push_back(make_pair(++m,0));
35 lst=m;
36 }
37 if (v.size()){
38 e[lst].push_back(make_pair(v.back(),dep[v.back()]-dep[k]));
39 v.pop_back();
40 if (v.size())e[lst].push_back(make_pair(v.back(),dep[v.back()]-dep[k]));
41 }
42 }
43 void build(){
44 m=n;
45 memset(head,-1,sizeof(head));
46 for(int i=1;i<n;i++){
47 scanf("%d%d%d",&x,&y,&z);
48 add(x,y,z),add(y,x,z);
49 }
50 dfs(1,0,0);
51 E=0;
52 memset(head,-1,sizeof(head));
53 for(int i=1;i<=m;i++)assert(e[i].size()<=2);
54 for(int i=1;i<=m;i++)
55 for(int j=0;j<e[i].size();j++){
56 add(i,e[i][j].fi,e[i][j].se);
57 add(e[i][j].fi,i,e[i][j].se);
58 }
59 }
60 void get_sz(int k,int fa){
61 sz[k]=1;
62 for(int i=head[k];i!=-1;i=edge[i].nex)
63 if ((!vis[i>>1])&&(edge[i].to!=fa)){
64 get_sz(edge[i].to,k);
65 sz[k]+=sz[edge[i].to];
66 }
67 }
68 void get_rt(int k,int fa,int s){
69 for(int i=head[k];i!=-1;i=edge[i].nex)
70 if ((!vis[i>>1])&&(edge[i].to!=fa)){
71 get_rt(edge[i].to,k,s);
72 if ((s<=3*sz[edge[i].to]+1)&&(3*sz[edge[i].to]<=(s+1<<1)))rt=(i>>1);
73 }
74 }
75 void get_v(vi &v,int k,int fa,ll s){
76 if (k<=n){
77 val[k]=s+dep[k];
78 v.push_back(k);
79 }
80 for(int i=head[k];i!=-1;i=edge[i].nex)
81 if ((!vis[i>>1])&&(edge[i].to!=fa))get_v(v,edge[i].to,k,s+edge[i].len);
82 }
83 void divide(int k){
84 get_sz(k,0);
85 if (sz[k]==1)return;
86 get_rt(k,0,sz[k]);
87 k=rt,vis[k]=1;
88 vx.clear(),vy.clear();
89 get_v(vx,edge[k<<1].to,0,0);
90 get_v(vy,edge[(k<<1)|1].to,0,0);
91 ans=max(ans,calc(vx,vy)+edge[k<<1].len);
92 divide(edge[k<<1].to);
93 divide(edge[(k<<1)|1].to);
94 }
95 };
96 namespace T2{
97 int E,x,y,z,head[N],dfn[N],sh[N],f[N][20],st[N];
98 ll ans,dep[N],mx[N][2];
99 vi v0,v,e[N];
100 Edge edge[N<<1];
101 bool cmp(int x,int y){
102 return dfn[x]<dfn[y];
103 }
104 void add(int x,int y,int z){
105 edge[E]=Edge{head[x],y,z};
106 head[x]=E++;
107 }
108 int lca(int x,int y){
109 if (sh[x]<sh[y])swap(x,y);
110 for(int i=19;i>=0;i--)
111 if (sh[f[x][i]]>=sh[y])x=f[x][i];
112 if (x==y)return x;
113 for(int i=19;i>=0;i--)
114 if (f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
115 return f[x][0];
116 }
117 void dfs(int k,int fa,int s1,ll s2){
118 dfn[k]=++dfn[0],sh[k]=s1,dep[k]=s2;
119 f[k][0]=fa;
120 for(int i=1;i<20;i++)f[k][i]=f[f[k][i-1]][i-1];
121 for(int i=head[k];i!=-1;i=edge[i].nex)
122 if (edge[i].to!=fa)dfs(edge[i].to,k,s1+1,s2+edge[i].len);
123 }
124 void build(){
125 memset(head,-1,sizeof(head));
126 for(int i=1;i<n;i++){
127 scanf("%d%d%d",&x,&y,&z);
128 add(x,y,z),add(y,x,z);
129 }
130 dfs(1,1,0,0);
131 }
132 void build(vi v0){
133 bool flag=0;
134 for(int i=0;i<v0.size();i++)
135 if (v0[i]==1)flag=1;
136 if (!flag){
137 v0.push_back(1);
138 v.push_back(1);
139 }
140 sort(v0.begin(),v0.end(),cmp);
141 st[0]=st[1]=1;
142 for(int i=1;i<v0.size();i++){
143 int k=lca(v0[i],st[st[0]]);
144 while ((st[0]>1)&&(dfn[st[st[0]-1]]>=dfn[k])){
145 e[st[st[0]-1]].push_back(st[st[0]]);
146 st[0]--;
147 }
148 if (k!=st[st[0]]){
149 v.push_back(k);
150 e[k].push_back(st[st[0]]);
151 st[st[0]]=k;
152 }
153 st[++st[0]]=v0[i];
154 }
155 while (st[0]>1){
156 e[st[st[0]-1]].push_back(st[st[0]]);
157 st[0]--;
158 }
159 }
160 void dfs(int k){
161 for(int i=0;i<e[k].size();i++){
162 dfs(e[k][i]);
163 ans=max(ans,max(mx[k][0]+mx[e[k][i]][1],mx[k][1]+mx[e[k][i]][0])-(dep[k]<<1));
164 mx[k][0]=max(mx[k][0],mx[e[k][i]][0]);
165 mx[k][1]=max(mx[k][1],mx[e[k][i]][1]);
166 }
167 }
168 ll calc(vi vx,vi vy){
169 ans=-1e18,v0.clear();
170 for(int i=0;i<vx.size();i++)v0.push_back(vx[i]);
171 for(int i=0;i<vy.size();i++)v0.push_back(vy[i]);
172 v=v0,build(v0);
173 for(int i=0;i<v.size();i++)mx[v[i]][0]=mx[v[i]][1]=-1e18;
174 for(int i=0;i<vx.size();i++)mx[vx[i]][0]=val[vx[i]];
175 for(int i=0;i<vy.size();i++)mx[vy[i]][1]=val[vy[i]];
176 dfs(1);
177 for(int i=0;i<v.size();i++)e[v[i]].clear();
178 return ans;
179 }
180 };
181 ll calc(vi x,vi y){
182 return T2::calc(x,y);
183 }
184 int main(){
185 scanf("%d",&n);
186 T1::build();
187 T2::build();
188 for(int i=1;i<=n;i++)ans=max(ans,(T1::dep[i]-T2::dep[i])<<1);
189 T1::divide(1);
190 printf("%lld\n",(ans>>1));
191 return 0;
192 }
View Code
实际上，点分治也是可以做的
相比于边分治，点分治即要维护多棵子树中选两个不同的子树（而不是两个），那么仍暴力维护复杂度即退化为$o(n^{2}\log n)$，显然无法通过
考虑不断选择两棵最小的子树，并对这两棵子树内的点建虚树后求答案，求完后将两棵子树合并为一棵子树（注意这棵子树之后也可以参与合并）
关于复杂度，理性分析可以得到仍是$o(n\log^{2}n)$的（不优化虚树），感性理解一下即考虑合并过程的逆过程，不难发现与边分治等价，因此与边分治复杂度相同