Description
有一个节点数为 \(N\) 的树。边 \(i\) 连接 \(u_i\) 和 \(v_i\)，边的权值为 \(w_i\)。
\(Q\) 次询问，询问一共有两种。
1 i w ：改变第 \(i\) 条边的权值为 \(w\)。
2 u v ：输出 \(u\) 到 \(v\) 的路径距离。
数据范围：
\(1 \leq N \leq 2 \times 10^5\)
\(1 \leq u_i,v_i \leq N\)
\(1 \leq w_i \leq 10^9\)
\(1 \leq Q \leq 2 \times 10^5\)
Solution
经典树剖。如果不会树剖，移步模板题，还有边权转点权trick。
学完树剖后，这个题其实就一眼了。这个题更改权值时只更新一条边，不需要懒标记，给个数组存储一下第 \(i\) 条边的 \(u_i,v_i\)，暴力修改即可。
求路径距离的时候注意一下 LCA 处的权值不属于路径，要减去。
Code
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define next nxt
#define re register
#define il inline
const int N = 2e5 + 5;
const int M = 2e5 + 5;
using namespace std;
int max(int x,int y){return x > y ? x : y;}
int min(int x,int y){return x < y ? x : y;}
struct node{
int u,v,w,next;
}edge[M<<1],e[M<<1]; int head[N],num_edge;
int w[N],wt[N];
int n,m,u,v,ww,x,y,k,op;
int tree[N<<2];
int son[N],id[N],fa[N],tot,dep[N],siz[N],top[N];
il int read()
{
int f=0,s=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) f |= (ch=='-');
for(; isdigit(ch);ch=getchar()) s = (s<<1) + (s<<3) + (ch^48);
return f ? -s : s;
}
il void add(int from,int to,int dis)
{
edge[++num_edge] = (node){from,to,dis,head[from]};
head[from] = num_edge;
}
#define lc p<<1
#define rc p<<1|1
il void build(int p,int l,int r)
{
if(l == r)
{
tree[p] = wt[l];
return ;
}
int mid = (l+r) >> 1;
build(lc,l,mid);
build(rc,mid+1,r);
tree[p] = tree[lc] + tree[rc];
}
il void Modify(int nl,int nr,int l,int r,int p,int k)
{
if(l >= nl && r <= nr)
{
tree[p] = k;
return ;
}
int mid = (l+r) >> 1;
if(nl <= mid) Modify(nl,nr,l,mid,lc,k);
if(nr > mid) Modify(nl,nr,mid+1,r,rc,k);
tree[p] = tree[lc] + tree[rc];
}
il int Query(int nl,int nr,int l,int r,int p)
{
int res = 0;
if(l >= nl && r <= nr) return tree[p];
int mid = (l+r) >> 1;
if(nl <= mid) res += Query(nl,nr,l,mid,lc);
if(nr > mid) res += Query(nl,nr,mid+1,r,rc);
return res;
}
/*------------------------------------------*/
il void dfs1(int x,int f)
{
dep[x] = dep[f] + 1 , fa[x] = f , siz[x] = 1;
for(re int i=head[x];i;i=edge[i].next)
{
int y = edge[i].v , ww = edge[i].w;
if(y == f) continue;
dfs1(y,x);
w[y] = ww;
siz[x] += siz[y];
if(siz[son[x]] < siz[y]) son[x] = y;
}
}
il void dfs2(int x,int topf)
{
id[x] = ++tot , wt[tot] = w[x] , top[x] = topf;
if(!son[x]) return ;
dfs2(son[x],topf);
for(re int i=head[x];i;i=edge[i].next)
{
int y = edge[i].v;
if(y == fa[x] || y == son[x]) continue;
dfs2(y,y);
}
}
il void Modify_way(int x,int y,int k)
{
while(top[x] != top[y])
{
if(dep[top[x]] < dep[top[y]]) swap(x,y);
Modify(id[top[x]],id[x],1,n,1,k);
x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x,y);
if(x == y) return ;
Modify(id[x]+1,id[y],1,n,1,k);
}
il int Query_way(int x,int y)
{
int res = 0;
while(top[x] != top[y])
{
if(dep[top[x]] < dep[top[y]]) swap(x,y);
res += Query(id[top[x]],id[x],1,n,1);
x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x,y);
res += Query(id[x],id[y],1,n,1);
res -= Query(id[x],id[x],1,n,1);
return res;
}
signed main()
{
n = read();
for(re int i=1;i<=n-1;i++)
{
u = read() , v = read() , ww = read();
add(u,v,ww) , add(v,u,ww);
e[i] = (node){u,v,0,0};
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n);
m = read();
for(re int i=1;i<=m;i++)
{
op = read() , x = read() , y = read();
if(op == 1) Modify_way(e[x].u,e[x].v,y);
if(op == 2) cout << Query_way(x,y) << "\n";
}
return 0;
}