[SPOJ375] QTREE - Query on a tree

Description

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
• 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.

題目大意

給定一棵樹，告訴了每條邊的權值，然後給出兩種操作：

(1)把第i條邊的權值改為val

(2)詢問a，b路徑上權值最大的邊

題解

樹鍊剖分教程http://blog.sina.com.cn/s/blog_7a1746820100wp67.html

學了樹鍊剖分，這種算法是把樹hash到了幾段連續的區間上，分重鍊和輕鍊為連續的區間，可以證明任何兩點間路徑都可以分為 logn 複雜度的重鍊和輕鍊，也就是連續區間，然後再用線段樹等算法在這些區間上處理問題。顯然本題也是這樣，剖分過程 O(n) 複雜度，兩次dfs，用在 logn 的複雜度套上線段樹 O(n∗logn) ，總複雜度是 O(n∗log2n)

代碼

#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = +;
const int INF = ;

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[N<<],next[N<<],w[N<<],edge;

struct Edge {
    int u,v,c;
}tmp[N<<];

void Init() {
    memset(head,-,sizeof head);memset(son,-,sizeof son);
    tim=;edge=;
}

void add_edge(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]=;
    for(int i=head[u];~i;i=next[i]) {
        int v=to[i];if(v!=father) {
            dfs1(v,u,d+);siz[u]+=siz[v];
            if(son[u]==- || 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]==-)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,m,rt<<1
#define rson m+1,r,rt<<1|1

int maxx[N<<];

void pushup(int rt) {
    maxx[rt]=std::max(maxx[rt<<],maxx[rt<<|]);
}

void build(int l,int r,int rt) {
    if(l==r) {
        maxx[rt]=num[l];return ;
    }
    int m=(l+r)>>;
    build(lson);build(rson);
    pushup(rt);
}

void update(int l,int r,int rt,int p,int val) {
    if(l==r) {
        maxx[rt]=val;return ;
    }
    int m=(l+r)>>;
    if(p<=m) 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 and r<=R) return maxx[rt];
    int m=(l+r)>>;
    int ret=-INF;
    if(L<=m) ret=std::max(ret,Query(lson,L,R));
    if(R>m) ret=std::max(ret,Query(rson,L,R));
    return ret;
}

void change(int x,int val) {
    if(dep[tmp[x].u]>dep[tmp[x].v])
        update(,n,,tid[tmp[x].u],val);
    else update(,n,,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]]) std::swap(x,y);
        ans=std::max(ans,Query(,n,,tid[top[x]],tid[x]));
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) std::swap(x,y);
    if(x!=y) ans=std::max(ans,Query(,n,,tid[x]+,tid[y]));
    return ans;
}

int main()
{
    char oper[];
    int a,b,c,t;
    scanf("%d",&t);
    while(t--)
    {
        Init();
        scanf("%d",&n);
        for(int i=; i<n; i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            tmp[i].u=a;tmp[i].v=b;tmp[i].c=c;
            add_edge(a,b,c);
        }
        dfs1(,,);
        dfs2(,);
        for(int i=;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(,n,);
        while()
        {
            scanf("%s",oper);
            if(oper[]=='D') break;
            scanf("%d%d",&a,&b);
            if(oper[]=='Q')
                printf("%d\n",query(a,b));
            else
                change(a,b);
        }
    }
    return ;
}