题意： 知道了一颗有  n 个节点的树和树上每条边的权值，对应两种操作：

          0 x        输出 当前节点到 x节点的最短距离，并移动到 x 节点位置

          1 x val   把第 x 条边的权值改为 val

 

题意： 知道了一颗有  n 个节点的树和树上每条边的权值，对应两种操作：

          0 x        输出 当前节点到 x节点的最短距离，并移动到 x 节点位置

          1 x val   把第 x 条边的权值改为 val

LCA +RMQ+树状数组

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int maxn = 2e5+100;int N,Q,S;//vector 
          
            G[maxn];struct edge{    int to,next,w;}e[2*maxn];int head[2*maxn],tot;void add_edge(int u,int v,int w){    e[tot].to = v;    e[tot].w = w;    e[tot].next = head[u];    head[u] = tot++;    e[tot].to = u;    e[tot].w = w;    e[tot].next = head[v];    head[v] = tot++;}int in[maxn],out[maxn],P[2*maxn],fa[maxn][30],dep[maxn],dis[maxn],cnt;void dfs(int u,int _fa,int _dep,int _dis){    in[u] = ++cnt;    P[cnt] = u;    fa[u][0] = _fa;    dis[u] = _dis;    dep[u] = _dep;    for(int i=head[u];~i;i=e[i].next)    {        int v = e[i].to;        if(v == _fa) continue;        dfs(v,u,_dep+1,_dis+e[i].w);    }    out[u] = ++cnt;}void debug(){    printf("in:\t");for(int i=1;i<=N;i++) printf("%d ",in[i]);puts("");    printf("out:\t");for(int i=1;i<=N;i++) printf("%d ",out[i]);puts("");    printf("p:\t");for(int i=1;i<=cnt;i++) printf("%d ",P[i]);puts("");    printf("dis:\t");for(int i=1;i<=N;i++) printf("%d ",dis[i]);puts("");    printf("dep:\t");for(int i=1;i<=N;i++) printf("%d ",dep[i]);puts("");    printf("edge:");for(int i=0;i
           
             dep[u]) swap(u,v); for(int k=0;k
            
             >k & 1 ) u = fa[u][k]; } if(u == v) return u; for(int k=m-1;k>=0;k--) { if(fa[u][k] != fa[v][k]) { u = fa[u][k]; v = fa[v][k]; } } return fa[u][0];}int c[2*maxn];int lowbit(int x) { return x&-x;}void init(){ memset(head,-1,sizeof head); memset(fa,-1,sizeof fa); memset(c,0,sizeof c); memset(in,0,sizeof in); memset(out,0,sizeof out); tot = 0; cnt = 0;}void add(int x,int d){ while(x) { c[x] += d; x -= lowbit(x); }}void add_seg(int l,int r,int d){ add(r,d); add(l-1,-d);}int sum(int x){ int res = 0; //printf("u:%d ",P[x]); while(x <= cnt) { res += c[x]; x += lowbit(x); } //printf("res:%d\n",res); return res;}int dist(int x){ if(x == -1) return 0; return sum(in[x]) + dis[x];}int main(){ //freopen("input.txt","r",stdin); while(~scanf("%d%d%d",&N,&Q,&S)) { init(); for(int i=0,u,v,w;i
            
           
          
         
        
       
      

 

树链部分

#include
      
       #include
       
        #include
        
         #define lson l, m, rt << 1#define rson m + 1, r, rt << 1 | 1using namespace std;typedef long long ll;const int MAXN = 2e5 + 10;int n, q, s;int fa[MAXN]; // fa[v]: v 的父亲int dep[MAXN]; // dep[v]: v 的深度（根深度为１）int siz[MAXN]; // : 以 v 为根的子树的节点数int son[MAXN]; // : 重儿子，siz[u] 为 v　的子节点中 siz　值最大的，那么 u 就是 v 的重儿子int top[MAXN]; // : 表示 v 所在的重链的顶端节点int w[MAXN]; // : 表示 v 与其父亲节点的连边在线段树中的位置int num; // 将树映射到线段树上的标号int cnt, head[MAXN];struct Edge {    int to, next;}edge[MAXN];struct E {    int u, v, c;}e[MAXN];void addedge(int u, int v) {    edge[cnt].to = v;    edge[cnt].next = head[u];    head[u] = cnt++;}void dfs(int u) {    siz[u] = 1; son[u] = 0;    for(int i = head[u]; ~i; i = edge[i].next) {        if(edge[i].to != fa[u]) {            fa[edge[i].to] = u;            dep[edge[i].to] = dep[u] + 1;            dfs(edge[i].to);            if(siz[edge[i].to] > siz[son[u]]) son[u] = edge[i].to;            siz[u] += siz[edge[i].to];        }    }}void build_tree(int u, int tp) {    w[u] = ++num; top[u] = tp;    if(son[u]) build_tree(son[u], top[u]); // 使重链各边在线段树中呈连续分布    for(int i = head[u]; ~i; i = edge[i].next) {        int v = edge[i].to;        if(v != son[u] && v != fa[u])            build_tree(v, v);    }}ll sum[MAXN];void pushUp(int rt) {    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];}void build(int l, int r, int rt) {    sum[rt] = 0;    if(l == r) return;    int m = (l + r) / 2;    build(lson); build(rson);}void update(int p, int c, int l, int r, int rt) {    if(l == r) {        sum[rt] = c;        return;    }    int m = (l + r) / 2;    if(m >= p) update(p, c, lson);    else update(p, c, rson);    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) / 2;    ll res = 0;    if(m >= L) res += query(L, R, lson);    if(m < R) res += query(L, R, rson);    return res;}void change(int v, int c) {    if(dep[e[v].u] > dep[e[v].v]) update(w[e[v].u], c, 1, n, 1);    else update(w[e[v].v], c, 1, n, 1);}ll seek(int v, int u) {    int t1 = top[v], t2 = top[u];    ll res = 0;    while(t1 != t2) {        if(dep[t1] < dep[t2]) {            swap(t1, t2); swap(v, u);        }        res += query(w[t1], w[v], 1, n, 1);        v = fa[t1]; t1 = top[v];    }    if(v == u) return res;    if(dep[v] > dep[u]) swap(v, u);    return res + query(w[son[v]], w[u], 1, n, 1);}int main() {    memset(head, -1, sizeof head);    cnt = num = 0;    scanf("%d%d%d", &n, &q, &s);    for(int i = 1;  i < n; i++) {        scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].c);        addedge(e[i].u, e[i].v);        addedge(e[i].v, e[i].u);    }    dfs(1);    build_tree(1, 1);    build(1, n, 1);    for(int i = 1; i < n; i++) {        if(dep[e[i].u] > dep[e[i].v]) update(w[e[i].u], e[i].c, 1, n, 1);        else update(w[e[i].v], e[i].c, 1, n, 1);    }    while(q--) {        int cc;        int x, y;        scanf("%d", &cc);        if(cc) {            scanf("%d%d", &x, &y);            change(x, y);        } else {            scanf("%d", &x);            printf("%lld\n", seek(s, x));            s = x;        }    }    return 0;}