QTREE - Query on a tree

no tags
You are given a tree (an acyclic undirected connected graph) with N nodes, and edges numbered 1, 2, 3…N-1.

We will ask you to perfrom some instructions of the following form:

CHANGE i ti : change the cost of the i-th edge to ti
or
QUERY a b : ask for the maximum edge cost on the path from node a to node b
Input

The first line of input contains an integer t, the number of test cases (t <= 20). t test cases follow.

For each test case:

In the first line there is an integer N (N <= 10000),
In the next N-1 lines, the i-th line describes the i-th edge: a line with three integers a b c denotes an edge between a, b of cost c (c <= 1000000),
The next lines contain instructions “CHANGE i ti” or “QUERY a b”,
The end of each test case is signified by the string “DONE”.
There is one blank line between successive tests.

Output

For each “QUERY” operation, write one integer representing its result.

Example

Input:
1

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE

Output:
1
3
Submit solution!

这道题只是把点权改成了边权，在做的时候只是维护一下这个点的上一条边和重链顶端的下一条边就好了。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=10100;
int n,point[N],next[N*10],tot=1,siz[N]={0},fa[N][20]={0},son[N]={0};
int deep[N]={0},num=0,pos[N]={0},belong[N]={0},r[N]={0},map[N]={0},tr[N*4];
struct S{
    int st,en,va;
}aa[N*10];
bool use[N];
inline void add(int x,int y,int z)
{
    tot+=1;next[tot]=point[x];point[x]=tot;
    aa[tot].st=x;aa[tot].en=y;aa[tot].va=z;
    tot+=1;next[tot]=point[y];point[y]=tot;
    aa[tot].st=y;aa[tot].en=x;aa[tot].va=z;
}
inline void dfs_1(int x)
{
    int i;
    siz[x]=1;
    use[x]=false;
    for(i=1;i<=14;++i){
        if(deep[x]<(1<<i)) break;
        fa[x][i]=fa[fa[x][i-1]][i-1];
    }
    for(i=point[x];i;i=next[i])
      if(use[aa[i].en]){
        fa[aa[i].en][0]=x;
        deep[aa[i].en]=deep[x]+1;
        dfs_1(aa[i].en);
        siz[x]+=siz[aa[i].en];
      }
}
inline void dfs_2(int x,int y)
{
    int i,k=0;
    num+=1;
    belong[x]=y;
    for(i=point[x];i;i=next[i]){
        if(deep[aa[i].st]>deep[aa[i].en]) map[aa[i].st]=i>>1;
        else map[aa[i].en]=i>>1;
    }
    for(i=point[x];i;i=next[i])
      if(deep[x]<deep[aa[i].en]&&siz[k]<siz[aa[i].en])
        k=aa[i].en,son[x]=i>>1,pos[i>>1]=num;
    if(k==0) {num-=1; return ;}
    dfs_2(k,y);
    for(i=point[x];i;i=next[i])
      if(deep[x]<deep[aa[i].en]&&k!=aa[i].en)
        num+=1,pos[i>>1]=num,dfs_2(aa[i].en,aa[i].en);
}
inline int LCA(int x,int y)
{
    int i;
    if(deep[x]<deep[y])swap(x,y);
    int t=deep[x]-deep[y];
    for(i=0;i<=14;++i)
        if(t&(1<<i))x=fa[x][i];
    for(i=14;i>=0;--i)
        if(fa[x][i]!=fa[y][i]) 
        {x=fa[x][i];y=fa[y][i];}
    if(x==y)return x;
    else return fa[x][0];
}
#define mid (l+r)/2
#define L k<<1,l,mid
#define R k<<1|1,mid+1,r
inline void insert(int k,int l,int r,int x,int y)
{
    if(l==r&&l==x){
        tr[k]=y;
        return ;
    }
    if(x<=mid) insert(L,x,y);
    else insert(R,x,y);
    tr[k]=max(tr[k<<1],tr[k<<1|1]);
}
inline int qurry(int k,int l,int r,int x,int y)
{
    int maxn=-210000000;
    if(x<=l&&y>=r) return tr[k];
    if(x<=mid) maxn=max(maxn,qurry(L,x,y));
    if(y>mid) maxn=max(maxn,qurry(R,x,y));
    return maxn;
}
inline int ask(int x,int y)
{
    int maxn=-210000000,z;
    if(map[x]==0) return maxn;
    if(belong[x]==x&&x!=y){
        maxn=max(maxn,r[map[x]]);
        x=fa[x][0];
    }
    if(map[x]==0) return maxn;
    while(belong[x]!=belong[y]){
        maxn=max(maxn,qurry(1,1,n-1,pos[son[belong[x]]],pos[map[x]]));
        z=fa[belong[x]][0];
        maxn=max(maxn,qurry(1,1,n-1,pos[map[belong[x]]],pos[map[belong[x]]]));
        x=z;
    }
    if(map[x]==0) return maxn;
    maxn=max(maxn,qurry(1,1,n-1,pos[son[y]],pos[map[x]]));
    return maxn;
}
int main()
{
    int i,j,x,y,z;
    char ch[10];
    memset(use,1,sizeof(use));
    scanf("%d",&n);
    for(i=1;i<n;++i){
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);r[i]=z;
    }
    dfs_1(1);
    dfs_2(1,1);
    for(i=1;i<n;++i) insert(1,1,n-1,pos[i],r[i]);
    while(scanf("%*c%s",&ch)){
        if(ch[0]==‘D‘) break;
        scanf("%d%d",&x,&y);
        if(ch[0]==‘C‘) insert(1,1,n-1,pos[x],y),r[x]=y;
        else{
            int lca=LCA(x,y);
            printf("%d\n",max(ask(x,lca),ask(y,lca)));
        }
    }
}