题意：给定一棵有n（ n < 100001 ）个结点的带边权的树,处理以下一共q（q < 100001）个操作：
1，改变树的一条边的权；
2，求给定点和某点的距离，后者是编号为1的结点，若是第一次执行操作2，否则为上次执行操作2的给定点。
分析：如果没有操作1 的话，也就是边的权值没有改变的话，是很常见的LCA转RMQ问题； 如果边 的权值发生改变了的话，是否意味预处理出来的数据都没用了呢？其实不然，改变一条边的权值，对那些边造成影响是固定的，也就是说，如果欧拉序列固定了，改变了一条边的权值，那么整个子树的dis[]值（到根节点的距离）都改变了，而在欧拉序列中，整个子树是连续的，，只需要顺便记录每一个节点在欧拉序列中的起始和终点位置，那么改变的也就是一个欧拉序列的一个区间了。。。
可以用树状数组来维护一个dis1[i]，也就是在改变之后与原先的dis[i] 的差值。。
View Code
#include<iostream> #include<algorithm> #include<string.h> #include<math.h> #include<stdio.h> using namespace std; const int N = 100000+10; struct Edge { int v,nex,w; }E[N*2]; struct edge { int u,v; int w; }e[N]; int head[N],size,n; int F[2*N],B[2*N],pos_s[N],pos_e[N],dis[N],bn; int tree[2*N],dp[N*2][20]; bool vis[N]; void init() { memset(head,-1,sizeof(head)); memset(vis,false,sizeof(vis)); size=0; } void insert(int u,int v,int w) { E[size].v=v; E[size].w=w; E[size].nex=head[u]; head[u]=size++; } //dis[] 记录每一个节点到达根节点的距离 //F[]对应着欧拉序列,,B[] 是与欧拉序列对应的每一个点的深度（这是用过求LCA的） //pos_s[] 和 pos_e[]分别记录节点在欧拉序列的起始和终点位置 void dfs(int cur,int deep,int len) { vis[cur]=true; dis[cur]=len; F[bn]=cur; B[bn]=deep; pos_s[cur]=bn++; for(int i=head[cur];i!=-1;i=E[i].nex) { int v=E[i].v; if(!vis[v]) { dfs(v,deep+1,len+E[i].w); F[bn]=cur; B[bn]=deep; bn++; } } pos_e[cur]=bn-1; } void init_RMQ() { memset(dp,0,sizeof(dp)); for(int i=1;i<=bn;++i) dp[i][0]=i; for(int j=1;j<=log((double)(bn+1))/log(2.0);++j) { int limit=bn+1-(1<<j); for(int i=1;i<=limit;++i) { int x=dp[i][j-1]; int y=dp[i+(1<<(j-1))][j-1]; dp[i][j]=B[x]<B[y]?x:y; } } } int RMQ(int a,int b) { if(a>b) swap(a,b); int k=(int)(log((double)(b-a+1))/log(2.0)); int x=dp[a][k]; int y=dp[b+1-(1<<k)][k]; return B[x]<B[y]?x:y; } int lowbit(int x) { return x&(-x); } void modify(int x,int add) { while(x<2*n) { tree[x]+=add; x+=lowbit(x); } } int get_val(int x)//求单点 { int ret=0; while(x>0) { ret+=tree[x]; x-=lowbit(x); } return ret; } int main() { int Q,s; int a,c; int op; while(scanf("%d %d %d",&n,&Q,&s)==3) { init(); for(int i=1;i<n;++i) { scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w); insert(e[i].u,e[i].v,e[i].w); insert(e[i].v,e[i].u,e[i].w); } bn=1; dfs(1,0,0); --bn; init_RMQ(); memset(tree,0,sizeof(tree)); while(Q--) { scanf("%d",&op); if(op==0) { scanf("%d",&a); int t=RMQ(pos_s[s],pos_s[a]);//求出最近公共祖先在欧拉序列的下标 int ans=get_val(t)+dis[F[t]];//get_val（t） 得到的只是欧拉序列中下标为t的点到祖先的距离的改变值，还需要加上原先的距离 ans=get_val(pos_s[s])+dis[s]-2*ans; ans+=get_val(pos_s[a])+dis[a]; printf("%d\n",ans); s=a; } else { scanf("%d %d",&a,&c); int w=c-e[a].w,u;//发生改变的权值 e[a].w=c; if(dis[e[a].u]<dis[e[a].v])//判断应该改变的是哪个节点的子树 u=e[a].v; else u=e[a].u; int l=pos_s[u],r=pos_e[u]; //cout<<l<<' '<<r<<endl; modify(r+1,-w); modify(l,w);//这俩步操作改变的是区间[l,r]，对应的是欧拉序列的区间 } } } return 0; }