SPOJ QTREE Query on a tree 树链剖分

SPOJ QTREE Query on a tree

新的树链剖分模板实验

---

#include <bits/stdc++.h>
#define lson num<<1
#define rson num<<1|1
#define gl l,m,lson
#define gr m+1,r,rson
#define PARA int l=1,int r=n,int num=1


using namespace std;
const int MAXN = 1e4+100;


int n;
struct SegTree
{
    int st[MAXN<<2];
    void update(int pos,int v,PARA)
    {
        if(l==r)
            st[num]=v;
        else
        {
            int m=l+r>>1;
            if(pos<=m)
                update(pos,v,gl);
            else update(pos,v,gr);
            st[num]=max(st[lson],st[rson]);
        }
    }
    int query(int a,int b,PARA)
    {
        if(a<=l&&r<=b)
            return st[num];
        int m=l+r>>1;
        if(b<=m)
            return query(a,b,gl);
        else if(a>m)
            return query(a,b,gr);
        else
            return max(query(a,b,gl),query(a,b,gr));
    }
};


struct Graph
{
    SegTree tr;
    struct Edge
    {
        int to;
        int w;
        int next;
    } edges[MAXN<<1];
    int head[MAXN],edge;
    void init()
    {
        memset(head,-1,sizeof(head));
        cur=edge=0;
        wei[1]=0;
    }
    void addEdge(int u,int v,int w)
    {
        edges[edge].w=w,edges[edge].to=v,edges[edge].next=head[u],head[u]=edge++;
        edges[edge].w=w,edges[edge].to=u,edges[edge].next=head[v],head[v]=edge++;
    }
    int fa[MAXN],son[MAXN],dep[MAXN],wei[MAXN],num[MAXN];
    void build(int u=1,int f=0,int d=0)
    {
        dep[u] = d;
        fa[u] = f;
        son[u]=-1;
        num[u]=1;
        for(int i = head[u]; i != -1; i = edges[i].next)
        {
            int v = edges[i].to;
            if(v != f)
            {
                build(v,u,d+1);
                wei[v]=edges[i].w;
                num[u] += num[v];
                if(son[u] == -1 || num[v] > num[son[u]])
                    son[u] = v;
            }
        }
    }
    int seg[MAXN],top[MAXN],cur;
    void split(int u=1,int tp=1)
    {
        seg[u]=++cur;
        top[u]=tp;
        if(son[u]!=-1)
            split(son[u],tp);
        for(int i=head[u]; i!=-1; i=edges[i].next)
        {
            int v=edges[i].to;
            if(v==fa[u]||v==son[u])
                continue;
            split(v,v);
        }
    }
    void call()
    {
        init();
        int a,b,c;
        for(int i=1; i<n; i++)
            scanf("%d%d%d",&a,&b,&c),addEdge(a,b,c);
        build();
        split();
        for(int i=1; i<=n; i++)
            tr.update(seg[i],wei[i]);
    }
    int find(int va,int vb)
    {
        int f1=top[va],f2=top[vb],tmp=0;
        while (f1!=f2)
        {
            if (dep[f1]<dep[f2])
            {
                swap(f1,f2);
                swap(va,vb);
            }
            tmp=max(tmp,tr.query(seg[f1],seg[va]));
            va=fa[f1];
            f1=top[va];
        }
        if (va==vb) return tmp;
        if (dep[va]>dep[vb]) swap(va,vb);
        return max(tmp,tr.query(seg[son[va]],seg[vb]));
    }
    void update(int a,int v)
    {
        a--;
        a<<=1;
        int u=edges[a+1].to;
        if(dep[edges[a].to]>dep[edges[a+1].to])
            u=edges[a].to;
        tr.update(seg[u],v);
    }
} soul;


char s[111];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        soul.call();
        while(1)
        {
            scanf("%s",s);
            if(s[0]=='D')
                break;
            int a,b;
            scanf("%d%d",&a,&b);
            if(s[0]=='Q')
                printf("%d\n",soul.find(a,b));
            else
                soul.update(a,b);
        }
    }
    return 0;
}