题目链接
https://www.luogu.com.cn/problem/AT_abc294_g
分析
先不考虑修改。
设 \(dist_i\) 表示从根节点到第 \(i\) 号节点的距离，\(\operatorname{lca(u,v)}\) 表示树上两点 \(u,v\) 的最近公共祖先，那么 \(u,v\) 两点间的距离就是 \((dist_{\operatorname{lca(u,v)}}-dist_u)+(dist_{\operatorname{lca(u,v)}}-dist_v)\)，即 \(dist_u+dist_v-dist_{\operatorname{lca(u,v)}}\times 2\)。
对于修改操作，考虑使用 dfs 序。
设 \(in_i\) 表示节点 \(i\) 入栈的时间戳，\(out_i\) 表示节点 \(i\) 出栈的时间戳，那么节点 \(i\) 的子树在新的线性序列上对应的区间就是 \([in_i,out_i]\)。
对于一条要被修改的边，设 \(x_1\) 表示原来的权值，\(x_2\) 表示修改后的权值，\(son\) 表示这条边上远离根节点的端点，那么就可以将新的线性序列上的区间 \([in_{son},out_{son}]\) 都作 \(-x_1+x_2\) 的操作，即对节点 \(son\) 的子树上的每一个点到根节点的距离，都 \(-x_1\)（消除原来边的影响）在 \(+x_2\)（加上新边的权值）。
可以使用差分 + 树状数组快速实现对序列的区间修改。
本题中距离最多可达到 \(2 \times 10^{14}\)，需要开 long long。
细节内容见代码注释。
Code
#include<bits/stdc++.h>
#define i64 long long
#define min(x,y) ((x)<(y)?(x):(y))
using namespace std;
const int N=2e5;
int n,q;
int tot_edge,hd[N+5];
struct Edge{int frm,to;i64 val;int lst;}g[N*2+5];
void add_edge(int u,int v,i64 w){
g[++tot_edge]=Edge{u,v,w,hd[u]};
hd[u]=tot_edge;
}
int tim,inn[N+5],outt[N+5];
int dep[N+5],f[N+5][30];
//dfs 序 + LCA 预处理
void dfs(int x,int fa){
inn[x]=++tim;
dep[x]=dep[fa]+1,f[x][0]=fa;
for(int i=1;i<=25;++i)
f[x][i]=f[f[x][i-1]][i-1];
for(int i=hd[x];~i;i=g[i].lst)
if(g[i].to^fa)dfs(g[i].to,x);
outt[x]=tim;
return;
}
//倍增求 LCA
int Lca(int x,int y){
if(dep[x]<dep[y])x^=y,y^=x,x^=y;
for(int i=25;~i;--i)
if(dep[f[x][i]]>=dep[y])x=f[x][i];
if(x==y)return x;
for(int i=25;~i;--i)
if(f[x][i]^f[y][i])
x=f[x][i],y=f[y][i];
return f[x][0];
}
//树状数组
i64 tr[N+5];
int lowbit(int x){return x&-x;}
void upd(int x,i64 v){
for(int i=x;i<=n;i+=lowbit(i))
tr[i]+=v;
return;
}
i64 ask(int x){
i64 res=0;
for(int i=x;i;i-=lowbit(i))
res+=tr[i];
return res;
}
int main(){
ios::sync_with_stdio(false),
cin.tie(0),cout.tie(0);
memset(hd,-1,sizeof hd);
int op,x1,x2,x3;
cin>>n;
for(int i=1;i<n;++i){
cin>>x1>>x2>>x3;
add_edge(x1,x2,x3),
add_edge(x2,x1,x3);
}
dfs(1,0);
//预处理每个点到根节点的距离
for(int i=1;i<=tot_edge;i+=2){
x1=g[i].frm,x2=g[i].to;
//寻找远离根节点的端点
if(dep[x1]<dep[x2])
//相当于 swap(x1,x2)
x1^=x2,x2^=x1,x1^=x2;
//将子树上每一个点到根节点的距离都加上这条边的权值
upd(inn[x1],g[i].val),
upd(outt[x1]+1,-g[i].val);
}
cin>>q;
while(q--){
cin>>op>>x1>>x2;
//修改
if(op==1){
x1*=2;//链式前向星存的是双向边，应将编号 *2
int u=g[x1].frm,v=g[x1].to;
//找到远离根节点的端点
if(dep[u]<dep[v])u^=v,v^=u,u^=v;
//消除原边影响
upd(inn[u],-g[x1].val),
upd(outt[u]+1,g[x1].val);
//加上新边权值
upd(inn[u],x2),
upd(outt[u]+1,-x2);
g[x1].val=x2;
}
//查询
else{
x3=Lca(x1,x2);
cout<<ask(inn[x1])+ask(inn[x2])-ask(inn[x3])*2<<'\n';
}
}
return 0;
}