题解 P6845 【[CEOI2019] Dynamic Diameter】
NashChen
·
·
题解
题意
一棵有 N 个点，边权可修改而形态不变的树，强制在线求直径。操作数为 Q 。
N,Q \leq 10^5
题解
那一天，人类重新想起了被 NOIP2018D2T3 支配的恐惧
动态dp当然是一种解法，但是这道题更多地是让我学会了欧拉序和线段树的高级使用方法。
这道题的思路是用欧拉序将树上问题转为区间最值问题。
欧拉序谁都会，难点是普及知识点线段树啊。
我们都知道欧拉序是用来求 lca 的，但是比较少用它来处理其他的树上问题。
对有根树，定义 dis[u] 为从 u 到根的距离。那么两点 (u,v) 间的距离就是
dis[u]+dis[v]-2\times dis[lca(u,v)]
对给定树求出欧拉序 Eul[i] 。设点 u,v 在欧拉序上的任意一个位置是 l,r ，那么有
dis[lca(u,v)]=\min_{l \leq k \leq r}\{dis[Eul[k]]\}
维护一条长为 2N-1 的序列 A[i]= dis[Eul[i]] 。所以求直径的问题可以转化为求
\max_{1\leq l\leq r\leq 2N-1} \{A[l]+A[r]-2\times\min_{l \leq k \leq r}\{A[k]\}\}
那么，用线段树怎么维护这个东西呢？这就是这道题的精髓。
上式是三个变量的最值式，考虑分治策略，多记录一些值来减少式子的变量。线段树其实就是一种分治思想的体现。
设
Diameter[L,R]=\max_{L\leq l\leq r\leq R} \{A[l]+A[r]-2\times\min_{l \leq k \leq r}\{A[k]\}\}
直径就是 Diameter[1,2N-1]
考虑固定 l ，式子可以变为 (k,r) 两个变量。如果能维护区间内下式的值
rmax[l,r]=A[i]-2\times\min_{i \leq j}\{A[j]\},\quad (l\leq i \leq j \leq r)
根据对称性，也构造一个
lmax[l,r]=A[i]-2\times\min_{i \geq j}\{A[j]\},\quad (l\leq j \leq i \leq r)
设 m 为 (l,r) 中点，考虑 (l,k,r) 和 m 的关系，那么就有
Diameter[m+1,R] & (m<l\leq k\leq r)\\
max[L,m]+rmax[m+1,R] & (l\leq m<k\leq r)\\
lmax[L,m]+max[m+1,R] & (l\leq k\leq m<r)\\
Diameter[L,m] & (l\leq k\leq r\leq m)\\
\end{cases}
而我们注意到 rmax 也能用这种思想求出
设 m 为 (l,r) 中点，考虑 (l,r) 和 m 的关系，那么就有
rmax[m+1,R] & (m<l\leq r)\\
max[L,m]-2\times min[m+1,R] & (l\leq m<r)\\
rmax[L,m] & (l\leq r\leq m)\\
\end{cases}
至此，我们构造出了 $Diameter[L,R]$ 随线段树的维护方法。
因为修改边权只对这条边**深度较深一段的子树**造成影响，而子树可以转化为**欧拉序上的一段区间**的修改。记录每个点对应的子树区间，也就是在欧拉序上的最早和最晚出现的位置，就可以将**边权修改**也转化为**区间操作**。
只需要记录 $min,max,lmax,rmax,Diameter$ 五个值，再记录区间修改的懒标记 $Add$，就可以完美地维护这道题的信息了。
具体细节见代码。
## 代码
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN= 800005;
int N,M,head[MAXN],nex[MAXN],targ[MAXN],cur;
int fa[MAXN],EO[MAXN],lb[MAXN],rb[MAXN],cnt;
long long dis[MAXN];
int weig[MAXN],son[MAXN];
long long len[MAXN],MaxW,lastans;
long long minx[MAXN],maxx[MAXN],lmax[MAXN],rmax[MAXN],diam[MAXN],Add[MAXN];
void editdata(int k,long long c){
minx[k]+= c;
maxx[k]+= c;
lmax[k]-= c;
rmax[k]-= c;
Add[k]+= c;
return;
}
void pushdown(int k){
if(!Add[k]) return;
editdata(k<<1,Add[k]);
editdata(k<<1|1,Add[k]);
Add[k]= 0;
return;
}
void pushup(int k){
minx[k]= min(minx[k<<1],minx[k<<1|1]);
maxx[k]= max(maxx[k<<1],maxx[k<<1|1]);
lmax[k]= max(max(lmax[k<<1],lmax[k<<1|1]),maxx[k<<1]-2*minx[k<<1|1]);
rmax[k]= max(max(rmax[k<<1],rmax[k<<1|1]),maxx[k<<1|1]-2*minx[k<<1]);
diam[k]= max(max(diam[k<<1],diam[k<<1|1]),max(maxx[k<<1]+rmax[k<<1|1],lmax[k<<1]+maxx[k<<1|1]));
return;
}
void updateSegtree(int a,int b,long long c,int k,int l,int r){
if(a<=l && r<=b){
editdata(k,c);
return;
}
if(r<a || b<l) return;
if(l<r) pushdown(k);
int mid= (l+r)>>1;
updateSegtree(a,b,c,k<<1,l,mid);
updateSegtree(a,b,c,k<<1|1,mid+1,r);
pushup(k);
return;
}
void buildSegtree(int k,int l,int r){
if(l==r){
maxx[k]= minx[k]= dis[EO[l]];
lmax[k]= rmax[k]= -dis[EO[l]];
diam[k]= 0;
return;
}
int mid= (l+r)>>1;
buildSegtree(k<<1,l,mid);
buildSegtree(k<<1|1,mid+1,r);
pushup(k);
return;
}
void buildEO(int u){
EO[++cnt]= u;
lb[u]= cnt;
for(int e= head[u];e;e= nex[e]){
int v= targ[e];
if(fa[u]==v) continue;
fa[v]= u;son[(e-1)/2]= v;
dis[v]= dis[u]+weig[e];
buildEO(v);
EO[++cnt]= u;
}
rb[u]= cnt;
return;
}
void AddEdge(int u,int v,long long w){
nex[++cur]= head[u];
head[u]= cur;
targ[cur]= v;
weig[cur]= w;
return;
}
void Input(){
scanf("%d%d%lld",&N,&M,&MaxW);
for(int i=0;i<N-1;++i){
int x,y;long long z;
scanf("%d%d%lld",&x,&y,&z);
AddEdge(x,y,z);
AddEdge(y,x,z);
len[i]= z;
}
return;
}
int main(){
Input();
buildEO(1);
buildSegtree(1,1,cnt);
while(M--){
int e;long long d;
scanf("%d%lld",&e,&d);
e= (e+lastans)%(N-1);
d= (d+lastans)%MaxW;
updateSegtree(lb[son[e]],rb[son[e]],d-len[e],1,1,cnt);
len[e]= d;
printf("%lld\n",lastans= diam[1]);
}
return 0;
}
```