题意：
给出一棵n个节点的树，有m个操作，操作为将一条路径上的边权加一或询问某条边的权值。
题解：
树链剖分只能解决点权，面对边权的问题，我们可以将边权用它的儿子节点的点权存储，这样在修改和查询的时候跳过两个点的LCA，即可实现边权的修改。
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+100; typedef long long ll; int n,m; vector<int> g[maxn]; int son[maxn]; int id[maxn]; int fa[maxn]; int cnt; int dep[maxn]; int size[maxn]; int top[maxn]; int w[maxn]; int wt[maxn]; struct node { int l,r; ll sum; ll lazy; }segTree[maxn*4]; void build (int i,int l,int r) { segTree[i].l=l; segTree[i].r=r; if (l==r) { segTree[i].sum=wt[l]; return; } int mid=(l+r)>>1; build(i<<1,l,mid); build(i<<1|1,mid+1,r); segTree[i].sum=segTree[i<<1].sum+segTree[i<<1|1].sum; } void spread (int i) { if (segTree[i].lazy) { segTree[i<<1].sum+=segTree[i].lazy*(segTree[i<<1].r-segTree[i<<1].l+1); segTree[i<<1|1].sum+=segTree[i].lazy*(segTree[i<<1|1].r-segTree[i<<1|1].l+1); segTree[i<<1].lazy+=segTree[i].lazy; segTree[i<<1|1].lazy+=segTree[i].lazy; segTree[i].lazy=0; } } void update (int i,int l,int r,int val) { if (l<=segTree[i].l&&segTree[i].r<=r) { segTree[i].sum+=val*(segTree[i].r-segTree[i].l+1); segTree[i].lazy+=val; return; } spread(i); int mid=(segTree[i].l+segTree[i].r)>>1; if (l<=mid) update(i<<1,l,r,val); if (r>mid) update(i<<1|1,l,r,val); segTree[i].sum=segTree[i<<1].sum+segTree[i<<1|1].sum; } ll query (int i,int l,int r) { if (l<=segTree[i].l&&r>=segTree[i].r) return segTree[i].sum; spread(i); int mid=(segTree[i].l+segTree[i].r)>>1; ll ans=0; if (l<=mid) ans+=query(i<<1,l,r); if (r>mid) ans+=query(i<<1|1,l,r); return ans; } ll qRange (int x,int y) { int ans=0; while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); ans+=query(1,id[top[x]],id[x]); x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); ans+=query(1,id[x],id[y]); return ans; } void upRange (int x,int y,int k) { while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); update(1,id[top[x]],id[x],k); x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); update(1,id[x],id[y],k); } int lca (int x,int y) { for (;top[x]!=top[y];dep[top[x]]>dep[top[y]]?x=fa[top[x]]:y=fa[top[y]]); return dep[x]<dep[y]?x:y; } void dfs1 (int x,int f,int deep) { dep[x]=deep; fa[x]=f; size[x]=1; int maxson=-1; for (int y:g[x]) { if (y==f) continue; dfs1(y,x,deep+1); size[x]+=size[y]; if (size[y]>maxson) son[x]=y,maxson=size[y]; } } void dfs2 (int x,int topf) { id[x]=++cnt; wt[cnt]=w[x]; top[x]=topf; if (!son[x]) return; dfs2(son[x],topf); for (int y:g[x]) { if (y==fa[x]||y==son[x]) continue; dfs2(y,y); } } int main () { scanf("%d%d",&n,&m); for (int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); g[x].push_back(y); g[y].push_back(x); } dfs1(1,0,1); dfs2(1,1); build(1,1,n); while (m--) { string ch; int x,y; cin>>ch>>x>>y; if (ch=="P"){ int wjm=lca(x,y); upRange(x,y,1); upRange(wjm,wjm,-1); } else { int t1=qRange(x,y); int wjm=lca(x,y); int t2=qRange(wjm,wjm); printf("%d ",t1-t2); } } }