SPOJ Query on a tree 树链剖分水题

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

模板题
2种操作：
1.把第i条边的边权更改为v
2.查询路径u，v中最大的边权

注意：是边权，所以查询时候u，v的lca不能包括进来
因为lca所表示的边权并没有在u，v的路径中

树链剖分+线段树(单点更新，区间查询)
线段树连lazy都不用

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define LL long long

#define debug printf("eeeeeeeeeeeeeeeeeeeee")

#define lson l,m,rt<<1

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

using namespace std;

const int maxn=1e4+;

const int inf=0x3f3f3f3f;

int dep[maxn];

int son[maxn];

int siz[maxn];

int top[maxn];

int fa[maxn];

int chg[maxn];

int rev[maxn];

int cost[maxn];

int e[maxn][];

struct Edge

{

    int to,next;

};

Edge edge[maxn<<];

int head[maxn];

int tot;

int ma[maxn<<];

void init()

{

    memset(head,-,sizeof head);

    tot=;

}

void addedge(int u,int v)

{

    edge[tot].to=v;

    edge[tot].next=head[u];

    head[u]=tot++;

}

void solve(int );

int main()

{

    int test;

    scanf("%d",&test);

    while(test--){

        int n;

        init();

        scanf("%d",&n);

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

            scanf("%d %d %d",&e[i][],&e[i][],&e[i][]);

            addedge(e[i][],e[i][]);

            addedge(e[i][],e[i][]);

        }

        solve(n);

    }

    return ;

}

void dfs0(int u,int pre)

{

    fa[u]=pre;

    siz[u]=;

    dep[u]=dep[pre]+;

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

        int v=edge[i].to;

        if(v==pre)

            continue;

        dfs0(v,u);

        siz[u]+=siz[v];

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

            son[u]=v;

    }

}

void dfs1(int u,int tp)

{

    top[u]=tp;

    chg[u]=++tot;

    rev[tot]=u;

    if(son[u]==-)

        return ;

    dfs1(son[u],tp);

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

        int v=edge[i].to;

        if(v==fa[u] || v==son[u])

            continue;

        dfs1(v,v);

    }

}

void pushup(int rt)

{

    ma[rt]=max(ma[rt<<],ma[rt<<|]);

}

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

{

    if(l==r){

        ma[rt]=cost[rev[l]];

        return ;

    }

    int m=(l+r)>>;

    build(lson);

    build(rson);

    pushup(rt);

}

void update(int p,int add,int l,int r,int rt)

{

    if(l==r){

        ma[rt]=add;

        return ;

    }

    int m=(l+r)>>;

    if(p<=m)

        update(p,add,lson);

    else

        update(p,add,rson);

    pushup(rt);

}

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

{

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

        return ma[rt];

    }

    int m=(l+r)>>;

    int ret=-inf;

    if(L<=m)

        ret=max(ret,query(L,R,lson));

    if(R>m)

        ret=max(ret,query(L,R,rson));

    return ret;

}

int query_path(int u,int v)

{

    int ret=-inf;

    while(top[u]!=top[v]){

        if(dep[top[u]]<dep[top[v]])

            swap(u,v);

        ret=max(ret,query(chg[top[u]],chg[u],,tot,));

        u=fa[top[u]];

    }

    if(dep[u]<dep[v])

        swap(u,v);

    ret=max(ret,query(chg[v]+,chg[u],,tot,));

    return ret;

}

void solve(int n)

{

    memset(dep,,sizeof dep);

    memset(son,-,sizeof son);

    memset(cost,,sizeof cost);

    dfs0(,);

    tot=;

    dfs1(,);

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

        if(dep[e[i][]]>dep[e[i][]])

            swap(e[i][],e[i][]);

        cost[e[i][]]=e[i][];

    }

    build(,tot,);

    char str[];

    while(scanf("%s",str)){

        if(str[]=='D')

            break;

        int u,v;

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

        if(str[]=='Q'){

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

        }

        else{

            update(chg[e[u][]],v,,tot,);

        }

    }

    return ;

}

巴特西

SPOJ Query on a tree 树链剖分水题

Input

Output

Example

最新文章

热门文章

巴特西

SPOJ Query on a tree 树链剖分 水题

Input

Output

Example

最新文章

热门文章

SPOJ Query on a tree 树链剖分水题