SPOJ375(树链剖分)

题目：Query on a tree

题意：给定一棵树，告诉了每条边的权值，然后给出两种操作：

(1)把第i条边的权值改为val

(2)询问a，b路径上权值最大的边

分析：本题与HDU3966差不多，区别就是：HDU3966是告诉树中点权的值，这里是边权。

所以我们可以转化，用边的孩子节点来表示该边。

#include <iostream>

#include <string.h>

#include <algorithm>

#include <stdio.h>

using namespace std;

const int N=50010;

const int INF=1<<30;

int n,tim;

int num[N],siz[N],top[N],son[N];

int dep[N],tid[N],rank[N],fa[N];

int head[N],to[2*N],next[2*N],w[2*N],edge;

struct Edge

{

    int u,v,c;

};

Edge tmp[2*N];

void Init()

{

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

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

    tim=0;

    edge=0;

}

void addedge(int u,int v,int c)

{

    to[edge]=v,w[edge]=c,next[edge]=head[u],head[u]=edge++;

    to[edge]=u,w[edge]=c,next[edge]=head[v],head[v]=edge++;

}

//树链剖分部分

void dfs1(int u,int father,int d)

{

    dep[u]=d;

    fa[u]=father;

    siz[u]=1;

    for(int i=head[u]; ~i; i=next[i])

    {

        int v=to[i];

        if(v!=father)

        {

            dfs1(v,u,d+1);

            siz[u]+=siz[v];

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

                son[u]=v;

        }

    }

}

void dfs2(int u,int tp)

{

    top[u]=tp;

    tid[u]=++tim;

    rank[tid[u]]=u;

    if(son[u]==-1) return;

    dfs2(son[u],tp);

    for(int i=head[u]; ~i; i=next[i])

    {

        int v=to[i];

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

            dfs2(v,v);

    }

}

//线段树部分

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

int MAX[4*N];

void PushUP(int rt)

{

    MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]);

}

void Build(int l,int r,int rt)

{

    if(l==r)

    {

        MAX[rt]=num[l];

        return;

    }

    int mid=(l+r)>>1;

    Build(lson);

    Build(rson);

    PushUP(rt);

}

void Update(int l,int r,int rt,int p,int val)

{

    if(l==r)

    {

        MAX[rt]=val;

        return;

    }

    int mid=(l+r)>>1;

    if(p<=mid)

        Update(lson,p,val);

    else

        Update(rson,p,val);

    PushUP(rt);

}

int Query(int l,int r,int rt,int L,int R)

{

    if(L<=l&&R>=r)

        return MAX[rt];

    int mid=(l+r)>>1;

    int ret=-INF;

    if(L<=mid) ret=max(ret,Query(lson,L,R));

    if(R>mid)  ret=max(ret,Query(rson,L,R));

    return ret;

}

void Change(int x,int val)

{

    if(dep[tmp[x].u]>dep[tmp[x].v])

        Update(2,n,1,tid[tmp[x].u],val);

    else

        Update(2,n,1,tid[tmp[x].v],val);

}

int query(int x,int y)

{

    int ans=-INF;

    while(top[x]!=top[y])

    {

        if(dep[top[x]]<dep[top[y]]) swap(x,y);

        ans=max(ans,Query(2,n,1,tid[top[x]],tid[x]));

        x=fa[top[x]];

    }

    if(dep[x]>dep[y]) swap(x,y);

    if(x!=y) ans=max(ans,Query(2,n,1,tid[x]+1,tid[y]));

    return ans;

}

int main()

{

    char oper[15];

    int a,b,c,t;

    scanf("%d",&t);

    while(t--)

    {

        Init();

        scanf("%d",&n);

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

        {

            scanf("%d%d%d",&a,&b,&c);

            tmp[i].u=a;tmp[i].v=b;tmp[i].c=c;

            addedge(a,b,c);

        }

        dfs1(1,1,1);

        dfs2(1,1);

        //用边的孩子节点来表示该边

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

        {

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

                num[tid[tmp[i].u]]=tmp[i].c;

            else

                num[tid[tmp[i].v]]=tmp[i].c;

        }

        Build(2,n,1);

        while(1)

        {

            scanf("%s",oper);

            if(oper[0]=='D') break;

            scanf("%d%d",&a,&b);

            if(oper[0]=='Q')

                printf("%d\n",query(a,b));

            else

                Change(a,b);

        }

    }

    return 0;

}