题目来源：POJ 2763 Housewife Wind

题意：给你一棵树 2种操作0 x 求当前点到x的最短路 然后当前的位置为x; 1 i x 将第i条边的权值置为x

思路：树上两点u, v距离为d[u]+d[v]-2*d[LCA(u,v)] 现在d数组是变化的 对应每一条边的变化 他修改的是一个区间 用时间戳处理每个点管辖的区域 然后用线段树修改 线段树的叶子节点村的是根到每一个点的距离 求最近公共祖先没差别 只是堕落用线段树维护d数组

各种错误 4个小时 伤不起

#include 
  
   
#include 
   
     #include 
    
      using namespace std; const int maxn = 200010; struct edge { int u, v, w, next; }edges[maxn*2], e[maxn]; int E[maxn*2], H[maxn*2], I[maxn*2], L[maxn], R[maxn]; int dp[maxn*2][40]; int cnt, clock, dfn; int first[maxn]; int a[maxn<<2]; int b[maxn]; int add[maxn<<2]; int degree[maxn]; int vis[maxn]; void AddEdge(int u, int v, int w) { edges[cnt].u = u; edges[cnt].v = v; edges[cnt].w = w; edges[cnt].next = first[u]; first[u] = cnt++; edges[cnt].u = v; edges[cnt].v = u; edges[cnt].w = w; edges[cnt].next = first[v]; first[v] = cnt++; } void dfs(int u, int fa, int dep) { E[++clock] = u; H[clock] = dep; I[u] = clock; L[u] = ++dfn; b[dfn] = u; for(int i = first[u]; i != -1; i = edges[i].next) { int v = edges[i].v; if(v == fa) continue; if(vis[v]) continue; vis[v] = true; dfs(v, u, dep+1); E[++clock] = u; H[clock] = dep; } R[u] = dfn; } void RMQ_init(int n) { for(int i = 1; i <= n; i++) dp[i][0] = i; for(int j = 1; (1<
     
       r) swap(l, r); int len = r-l+1, k = 0; while((1<
      
       >1)); a[rt<<1|1] += add[rt]*(k>>1); add[rt<<1] += add[rt]; add[rt<<1|1] += add[rt]; add[rt] = 0; } } void build(int l, int r, int rt) { a[rt] = 0; add[rt] = 0; if(l == r) return; int m = (l + r) >> 1; build(l, m, rt<<1); build(m+1, r, rt<<1|1); } void update(int x, int y, int l, int r, int rt, int num) { if(l == x && r == y) { a[rt] += (r-l+1)*num; add[rt] += num; return; } pushdown(rt, l, r); int m = (l + r) >> 1; if(y <= m) update(x, y, l, m, rt<<1, num); else if(x > m) update(x, y, m+1, r, rt<<1|1, num); else { update(x, m, l, m, rt<<1, num); update(m+1, y, m+1, r, rt<<1|1, num); } a[rt] = a[rt<<1] + a[rt<<1|1]; } int query(int x, int l, int r, int rt) { if(l == r) { return a[rt]; } pushdown(rt, l, r); int m = (l + r) >> 1; int ans = 0; if(x <= m) ans = query(x, l, m, rt<<1); else ans = query(x, m+1, r, rt<<1|1); a[rt] = a[rt<<1] + a[rt<<1|1]; return ans; } int main() { int cas = 1; int T; //scanf("%d", &T); int s, to, root, n, q; while(scanf("%d %d %d", &n, &q, &s) != EOF) { memset(vis, 0, sizeof(vis)); memset(first, -1, sizeof(first)); memset(degree, 0, sizeof(degree)); clock = cnt = dfn = 0; build(1, n, 1); //for(int i = 1; i <= n; i++) // scanf("%d", &b[i]); for(int i = 1; i < n; i++) { int u, v, w; scanf("%d %d %d", &u, &v, &w); e[i].u = u; e[i].v = v; e[i].w = w; AddEdge(u, v, 0); degree[v]++; } for(int i = 1; i <= n; i++) if(!degree[i]) { vis[i] = true; dfs(i, -1, 0); root = i; break; } RMQ_init(2*n-1); //puts("1"); for(int i = 1; i < n; i++) { int u = e[i].u; int v = e[i].v; int w = e[i].w; //printf("***%d %d\n", L[v], R[v]); if(L[u] < L[v]) update(L[v], R[v], 1, n, 1, w); else update(L[u], R[u], 1, n, 1, w); } while(q--) { int x; scanf("%d", &x); if(!x) { scanf("%d", &to); int d1 = query(L[s], 1, n, 1); int d2 = query(L[to], 1, n, 1); int lca = RMQ(s, to); int d3 = query(L[lca], 1, n, 1); //printf("***%d %d %d\n", d1, d2, d3); printf("%d\n", d1+d2-2*d3); //printf("%d\n", dfn); s = to; } else { int i, w; scanf("%d %d", &i, &w); int x = w - e[i].w; e[i].w = w; int v = e[i].v; int u = e[i].u; if(L[u] < L[v]) update(L[v], R[v], 1, n, 1, x); else update(L[u], R[u], 1, n, 1, x); } } } return 0; }