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