SPOJ QTREE Query on a tree --树链剖分

题意：给一棵树，每次更新某条边或者查询u->v路径上的边权最大值。

解法：做过上一题，这题就没太大问题了，以终点的标号作为边的标号，因为dfs只能给点分配位置，而一棵树每条树边的终点只有一个。

询问的时候，在从u找到v的过程中顺便查询到此为止的最大值即可。

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <algorithm>

using namespace std;

#define N 10007

int siz[N];  //子树大小

int son[N];  //重儿子

int dep[N];  //深度

int pos[N];  //在线段树中的位置

int Top[N];  //所在重链的祖先

int fa[N];   //父节点

int ans[N];  //答案

int head[*N],tot,POS,n,m;

struct Edge

{

    int v,next;

}G[*N];

int tree[*N];

struct node

{

    int u,v,w;

}edge[N];

void init()

{

    POS = tot = ;

    memset(head,-,sizeof(head));

    memset(son,-,sizeof(son));

    memset(tree,,sizeof(tree));

}

void addedge(int u,int v)

{

    G[tot].v = v, G[tot].next = head[u], head[u] = tot++;

    G[tot].v = u, G[tot].next = head[v], head[v] = tot++;

}

void pushup(int rt)

{

    tree[rt] = max(tree[*rt],tree[*rt+]);

}

void update(int l,int r,int pos,int val,int rt)

{

    if(l == r)

    {

        tree[rt] = val;

        return;

    }

    int mid = (l+r)/;

    if(pos <= mid)

        update(l,mid,pos,val,*rt);

    else

        update(mid+,r,pos,val,*rt+);

    pushup(rt);

}

int query(int l,int r,int aa,int bb,int rt)

{

    if(aa <= l && bb >= r)

        return tree[rt];

    int mid = (l+r)/;

    if(bb <= mid) return query(l,mid,aa,bb,*rt);

    else if(aa > mid) return query(mid+,r,aa,bb,*rt+);

    return max(query(l,mid,aa,bb,*rt),query(mid+,r,aa,bb,*rt+));

}

void dfs(int u,int f)

{

    dep[u] = dep[f]+;

    siz[u] = ;

    for(int i=head[u];i!=-;i=G[i].next)

    {

        int v = G[i].v;

        if(v == f) continue;

        fa[v] = u;

        dfs(v,u);

        if(son[u] == - || siz[v] > siz[son[u]]) son[u] = v;

        siz[u] += siz[v];

    }

}

void dfs2(int u,int father)

{

    pos[u] = ++POS;

    Top[u] = father;

    if(son[u] != -) dfs2(son[u],father);

    for(int i=head[u];i!=-;i=G[i].next)

    {

        int v = G[i].v;

        if(v != fa[u] && v != son[u])

            dfs2(v,v);

    }

}

int ask(int u,int v)

{

    int fx = Top[u], fy = Top[v], maxi = ;

    while(fx != fy)

    {

        if(dep[fx] < dep[fy])

        {

            swap(u,v);

            swap(fx,fy);

        }

        maxi = max(maxi,query(,POS,pos[fx],pos[u],));

        u = fa[fx];

        fx = Top[u];

    }

    if(u == v) return maxi;

    if(dep[u] > dep[v]) swap(u,v);

    return max(maxi,query(,POS,pos[son[u]],pos[v],));

}

int main()

{

    int u,v,w,x,y,i,t;

    char ss[];

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        init();

        for(i=;i<n;i++)

        {

            scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);

            addedge(edge[i].u,edge[i].v);

        }

        dep[] = ;

        dfs(,);

        dfs2(,);

        for(i=;i<n;i++)

        {

            if(dep[edge[i].u] > dep[edge[i].v])

                swap(edge[i].u,edge[i].v);

            update(,POS,pos[edge[i].v],edge[i].w,);

        }

        while(scanf("%s",ss)!=EOF && ss[] != 'D')

        {

            if(ss[] == 'Q')

            {

                scanf("%d%d",&u,&v);

                printf("%d\n",ask(u,v));

            }

            else

            {

                scanf("%d%d",&x,&y);

                update(,POS,pos[edge[x].v],y,);

            }

        }

        if(t >= )

            puts("");

    }

    return ;

}