<题目链接>
题目大意：
给定一棵无向树，这棵树的有边权，这棵树的边的序号完全由输入边的序号决定。给你一个人的起点，进行两次操作：
一：该人从起点走到指定点，问你这段路径的边权总和是多少。
二：对指定序号的边的权值做一些改变。
解题分析：
本题用的是树链剖分，同时用线段树去维护剖分出的树链。并且，本题也是无向边权转点权的典型例题，这部分要重点掌握。
#include <cstdio> #include <cstring> #define Lson l,mid,rt<<1 #define Rson mid+1,r,rt<<1|1 using namespace std; const int M = 1e5+7; typedef long long ll; int cnt,tot,head[M],p[M]; int n,q,pos,pp; int sz[M],top[M],son[M],id[M],rnk[M],f[M],dep[M]; ll a[M]; //代表该点的权值 struct EDGE{ int v,next; ll w; }edge[M<<1]; struct Tree { ll sum; }tree[M<<2]; void init(){ tot=cnt=0; memset(head,-1,sizeof(head)); } void add(int u,int v,ll w){ edge[++cnt].v=v,edge[cnt].w=w,edge[cnt].next=head[u]; head[u]=cnt; } void fsd(int u,int fa){ //将边权转化为点权 for(int i=head[u];~i;i=edge[i].next){ int v=edge[i].v;ll w=edge[i].w; if(v==fa) continue; a[v]=w; p[(i-1)/2+1]=v; //(i-1)/2+1 为该边加入的实际序号,因为加入某条边的时候，是将该边正的存一遍，反向存一遍，同一条边在e[]数组中是临近的，所以这里可以这样求该边加入的序号 //这里感觉挺巧妙的,p[i]表示序号为i的边对应的点(该点点权表示该边边权) fsd(v,u); //继续向下延伸，将边权转化为点权 } return; } void dfs(int u,int fa,int d){ //将重儿子标记，以及一系列的预处理 sz[u]=1;f[u]=fa;son[u]=-1;dep[u]=d; for(int i=head[u];~i;i=edge[i].next){ int v=edge[i].v; if(v==fa) continue; dfs(v,u,d+1); sz[u]+=sz[v]; if(son[u]==-1||sz[v]>sz[son[u]]) son[u]=v; } return ; } void dfs1(int u,int t){ //将重链全部找出来 id[u]=++tot; rnk[tot]=u; top[u]=t; if(son[u]==-1) return ; dfs1(son[u],t); for(int i=head[u];~i;i=edge[i].next){ int v=edge[i].v; if(v==f[u]||v==son[u]) continue; dfs1(v,v); } return ; } void Pushup(int rt){ tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum; } void build(int l,int r,int rt){ tree[rt].sum=0; if(l==r){ tree[rt].sum=a[rnk[l]]; return ; } int mid=(l+r)>>1; build(Lson); build(Rson); Pushup(rt); } void update(int l,int r,int rt,int loc,ll v){ //单点更新 if(l==r){ tree[rt].sum=v; return ; } int mid=(l+r)>>1; if(loc<=mid) update(Lson,loc,v); else update(Rson,loc,v); Pushup(rt); } ll query(int L,int R,int l,int r,int rt){ if(L<=l&&r<=R){ return tree[rt].sum; } ll ans=0; int mid=(l+r)>>1; if(L<=mid) ans+=query(L,R,Lson); if(R>mid) ans+=query(L,R,Rson); return ans; } /*--树上路径边权总和查询 --*/ ll sum(int x,int y){ int fx=top[x],fy=top[y];ll res=0; while(fx!=fy){ //如果这两个点不在一条重链上则一直向上跳，并且不断更新 if(dep[fx]>dep[fy]){ res+=query(id[fx],id[x],1,n,1); //因为在线段树中，fx的编号一定比x编号小 x=f[fx],fx=top[x]; //从这条重链爬到父节点所在重链的链首上去 } else{ res+=query(id[fy],id[y],1,n,1); y=f[fy],fy=top[y]; } } if(x==y) return res; //!!!,当x==y的时候要特判一下 if(dep[x]<dep[y]) res+=query(id[son[x]],id[y],1,n,1); //!!!，这里要注意，因为本题将边权转化为点权，所以计算x-->y的边权值，相当于直接计算son[x]-->y的点权值总和 else res+=query(id[son[y]],id[x],1,n,1); return res; } int main(){ init(); scanf("%d%d%d",&n,&q,&pos); for(int i=1;i<n;i++){ int u,v;ll w; scanf("%d%d%lld",&u,&v,&w); add(u,v,w);add(v,u,w); } /*-- 将边权转化为点权 --*/ fsd(1,-1); //从标号为1的点开始将边权转化为点权，其实这里从哪个点为起点都无所谓 a[1]=0; //因为是以1为起点将边权转化为点权，所以1没有权值，这里将1的权值赋0 /*--树链剖分 --*/ dfs(1,-1,1); dfs1(1,1); build(1,n,1); //将剖分出的树链用线段树维护 while(q--){ int op; scanf("%d",&op); if(op==0){ //从当前点走到指定点的路径权值总和 int to; scanf("%d",&to); printf("%lld ",sum(pos,to)); pos=to; //更新该人的起点 } else{ int cal;ll w; scanf("%d%lld",&cal,&w); //cal为需要更新的边的序号 update(1,n,1,id[p[cal]],w); } } return 0; }
2018-09-10