题目传送门：POJ - 2763 Housewife Wind
题目大意：
存在一个树形图，一个人一开始在s点，树上每条边都有时间花费，现在存在两种操作
1、 0 u ：查询这个人从他当前的点到点u的时间花费
2、 1 i w ：将第i条路径的时间花费更改为w
分析：
树链剖分，维护边权，用每条边深度较大的节点记录该边的边权，将边权改为点权，之后
即可用线段树单点更新，区间查询维护。
在更新节点权值时，对深度较大的节点进行更新，因此用结构体数组保存边信息后，将深度
较大的点记录在e[i].u中，方便更新操作。
注：在查询x->y路径和时，当x和y在同一条重链时，x点记录的权值为x->fa[x]的值，所以需要
用到的是son[x]->y所记录的值。并且在查询x->y路径时，当最后x和y值相同，则直接返回答案
代码：
#include<cstdio> #include<iostream> #include<cstring> using namespace std; typedef long long ll; #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 const int MAX=100009; int head[MAX],cnt=0; int fa[MAX],deep[MAX],son[MAX],size[MAX],top[MAX],id[MAX],rk[MAX],tot; int n,q,s,u,v,w,x,y,op; int sum[MAX<<2],a[MAX]; struct Edge{ int next,to; }edge[MAX*2]; inline void add(int u,int v) { edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt++; } struct E{ int u,v,w; }e[MAX]; void dfs1(int u,int f,int d) { deep[u]=d; fa[u]=f; size[u]=1; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(v!=fa[u]) { dfs1(v,u,d+1); size[u]+=size[v]; if(son[u]==-1||size[v]>size[son[u]]) son[u]=v; } } } void dfstop(int u,int t) { top[u]=t; id[u]=tot++; rk[id[u]]=u; if(son[u]==-1)return; dfstop(son[u],t); for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(v!=fa[u]&&v!=son[u]) dfstop(v,v); } } void PushUp(int rt)//维护区间和 { sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void Build(int l,int r,int rt) { if(l==r) { sum[rt]=a[rk[l]]; return; } int m=l+r>>1; Build(ls);Build(rs); PushUp(rt); } void Update(int pos,int val,int l,int r,int rt)//单点更新 { if(l==r) { sum[rt]=val; return; } int m=l+r>>1; if(pos<=m)Update(pos,val,ls); else Update(pos,val,rs); PushUp(rt); } ll Query(int L,int R,int l,int r,int rt)//区间查询 { if(L<=l&&r<=R) return sum[rt]; int m=l+r>>1; ll ans=0; if(L<=m)ans+=Query(L,R,ls); if(R>m)ans+=Query(L,R,rs); return ans; } ll ssum(int x,int y) //查询x->y路径和 { ll ret=0; while(top[x]!=top[y]) { if(deep[top[x]]<deep[top[y]]) swap(x,y); ret+=Query(id[top[x]],id[x],1,tot,1); x=fa[top[x]]; } if(x==y)return ret; //！！！！ if(deep[x]>deep[y])swap(x,y); ret+=Query(id[son[x]],id[y],1,tot,1);//当x和y在同一条重链时，最后x->y的值记录在son[x]->y这个区间中 return ret; } void init() { memset(head,-1,sizeof(head));cnt=0; memset(son,-1,sizeof(son));tot=1; memset(deep,0,sizeof(deep)); memset(size,0,sizeof(size)); } int main() { scanf("%d%d%d",&n,&q,&s); init(); for(int i=1;i<n;i++) { scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); add(e[i].u,e[i].v),add(e[i].v,e[i].u); } dfs1(1,-1,0);dfstop(1,1); for(int i=1;i<n;i++) { if(deep[e[i].u]<deep[e[i].v])//将边上深度较大的点记录在e[i].u中 swap(e[i].u,e[i].v); a[e[i].u]=e[i].w; //将边的权值保存在深度较大的点上 } Build(1,tot,1); while(q--) { scanf("%d",&op); if(op) { scanf("%d%d",&x,&y); Update(id[e[x].u],y,1,tot,1); } else { scanf("%d",&x); printf("%lld ",ssum(s,x)); s=x; //更新当前位置 } } return 0; }
总结：维护边权时，用边上深度较深的点记录边的权值，将边权改为点权操作，为了方便操作，
通常将边上深度较大的点放在记录边数组的统一位置，如(u,v)u记录的都是深度较大的点。其他的
就大同小异了。
该题为树链剖分--维护边权和
树链剖分--维护边权最大值：[SPOJ - QTREE] Query on a tree 题解