[POJ 2763] 树状数组 LCA RMQ

题意：

给定一棵无根树(边无向)，你一开始在s点上。

每次有两种操作。

1、0 x

表示走到x点上

2、1 i w

将第i条边的权值变为w

分析：

首先如果定义一个根，且d[i]为i点到根的距离。

那么必有dis(i,j)=d[i]+d[j]-2*d[lca(i,j)]

先按dfs顺序把点放进一个队列，这样如果以某点为根的子树的结点就会连续排列。

这样如果把某一条边改变以后，就相当如把以深度较大的那个点的为根的子树的所有d值都变为那个值。

那么这样的话就可以用线段树或者树状数组实现了。

插曲：

WA了很多遍，一开始work里很多东西写错，后来发现LCA写错。

cai0715-problem-solutions数据结构部分正式结束。

code：

#include #include #define N 222222
struct gtp{int x,y,w,next;}g[N];
int n,q,cur,ls[N],e,dep[N],d[N];
int Ql[N],Qt=0,pl[N],pr[N],El[N],Et=0,R[N],log2[N];

struct rmqtype{
    int w[20][N],who[20][N];
    void build(){
        int maxk=log2[Et];
        for (int i=1;i<=Et;i++) {
            w[0][i]=dep[El[i]];
            who[0][i]=El[i];
        }
        for (int k=1;k<=maxk;k++){
            int t=1<            for (int i=1;i+(1<              if (w[k-1][i]                  w[k][i]=w[k-1][i];
                  who[k][i]=who[k-1][i];
              }
              else{
                  w[k][i]=w[k-1][i+t];
                  who[k][i]=who[k-1][i+t];
              }
        }
    }
    int lca(int l,int r){
        int t;
        if (r        t=log2[r-l+1];
        if (w[t][l]        return who[t][r-(1<    }
}rmq;

struct Tree_Array_Type{
    int a[N];
    void clear(){memset(a,0,sizeof(a));}
    void add(int pos,int x){
        for (int i=pos;i<=n;i+=(i & -i)) a[i]+=x;
    }
    int sum(int pos){
        int t=0;
        for (int i=pos;i>=1;i-=(i & -i)) t+=a[i];
        return t;
    }
}Tarr;

void addedge(int x,int y,int w){
    e++;
    g[e].x=x; g[e].y=y; g[e].w=w; g[e].next=ls[x]; ls[x]=e;
}

void init(){
    memset(ls,0,sizeof(ls));
    memset(dep,0,sizeof(dep));
    int pre=-1;
    for (int i=1;i<=N;i++)
      if ((1<<(pre+1))==i) log2[i]=++pre;
                      else log2[i]=pre;
    scanf("%d%d%d",&n,&q,&cur);
    for (int i=1;i<=n-1;i++){
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        addedge(x,y,w);
        addedge(y,x,w);
    }
}

void predfs(int p,int nowdep,int distance){
    El[++Et]=p;
    R[p]=Et;
    Ql[++Qt]=p;
    dep[p]=nowdep;
    pl[p]=Qt;
    d[p]=distance;
    for (int t=ls[p];t>0;t=g[t].next)
      if (dep[g[t].y]==0) {
          predfs(g[t].y,nowdep+1,distance+g[t].w);
          El[++Et]=p;
      }
    pr[p]=Qt;
}

void Build(){
    Tarr.clear();
    for (int i=1;i<=n;i++) {
        Tarr.add(pl[i],d[i]);
        Tarr.add(pl[i]+1,-d[i]);
    }
    rmq.build();
}

void work(){
    int op,x,y;
    for (int k=1;k<=q;k++){
        scanf("%d",&op);
        if (op==0){
           scanf("%d",&x);
           int fa=rmq.lca(R[cur],R[x]);
           printf("%dn",Tarr.sum(pl[cur])+Tarr.sum(pl[x])-2*Tarr.sum(pl[fa]));
           cur=x;
        }
        else{
            scanf("%d%d",&x,&y);
            int p=g[x*2].x;
            if (dep[g[x*2].x]            int change=y-g[x*2].w;
            Tarr.add(pl[p],change);
            Tarr.add(pr[p]+1,-change);
            g[x*2-1].w=y;
            g[x*2].w=y;
        }
    }
}

int main(){
    init();
    predfs(1,1,0);
    rmq.build();
    Build();
    work();
    return 0;
}