1583. [POJ3237]树的维护

http://www.cogs.pro/cogs/problem/problem.php?pid=1583

★★★☆ 输入文件：maintaintree.in 输出文件：maintaintree.out 简单对比
时间限制：5 s 内存限制：128 MB

【题目描述】

给你由N个结点组成的树。树的节点被编号为1到N，边被编号为1到N-1。每一条边有一个权值。然后你要在树上执行一系列指令。指令可以是如下三种之一：

CHANGE i v：将第i条边的权值改成v。

NEGATE a b：将点a到点b路径上所有边的权值变成其相反数。

QUERY a b：找出点a到点b路径上各边的最大权值。

【输入格式】

输入文件的第一行有一个整数N（N<=10000）。

接下来N-1行每行有三个整数a,b,c，代表点a和点b之间有一条权值为c的边。这些边按照其编号从小到大给出。

接下来是若干条指令（不超过10^5条），都按照上面所说的格式。

输入文件的最后一行是"DONE".

【输出格式】

对每个“QUERY”指令，输出一行，即路径上各边的最大权值。

【样例输入】

1 2 1

2 3 2

QUERY 1 2

CHANGE 1 3

QUERY 1 2

DONE

【样例输出】

【提示】

这里的输入输出格式和POJ上原题略有不同。

【来源】

POJ 3237 Tree

难点在于取相反数操作

记录下最大值和最小值，有取相反数操作时，就把两个值变成相反数，再交换两数的值就ok，然后给这个区间打上标记（线段树的lazy标记），以后访问或更改值时记得下传标记就好。

#include <stdio.h>

#include <iostream>

#include <algorithm>

#include <cstring>

using namespace std;

const int MAXN = ;

struct Edge{

    int to,next;

}edge[MAXN*];

int head[MAXN],tot;

int top[MAXN];//top[v]表示v所在的重链的顶端节点

int fa[MAXN]; //父亲节点

int deep[MAXN];//深度

int num[MAXN];//num[v]表示以v为根的子树的节点数

int p[MAXN];//p[v]表示v与其父亲节点的连边在线段树中的位置

int fp[MAXN];//和p数组相反

int son[MAXN];//重儿子

int pos;

void init(){

    tot = ;

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

    pos = ;

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

}

void addedge(int u,int v){

    edge[tot].to = v;edge[tot].next = head[u];head[u] = tot++;

}

void dfs1(int u,int v,int d){

    deep[v]=d;

    fa[v]=u;

    num[v]=;

    for(int i=head[v];i!=-;i=edge[i].next){

        int to=edge[i].to;

        if(to==u)continue;

        dfs1(v,to,d+);

        num[v]+=num[to];

        if(son[v]==-||num[son[v]]<num[to])son[v]=to;

    }

}

void dfs2(int u,int v){

    top[u]=v;

    p[u]=pos++;

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

    dfs2(son[u],v);

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

        int to=edge[i].to;

        if(to==fa[u]||to==son[u])continue;

        dfs2(to,to);

    }

}

//线段树

struct Node{

    int l,r;

    int Max;

    int Min;

    int ne;

}tr[MAXN*];

void build(int i,int l,int r){

    tr[i].l = l;

    tr[i].r = r;

    tr[i].Max = ;

    tr[i].Min = ;

    tr[i].ne = ;

    if(l == r)return;

    int mid = (l+r)/;

    build(i<<,l,mid);

    build((i<<)|,mid+,r);

}

void push_up(int i)

{

    tr[i].Max = max(tr[i<<].Max,tr[(i<<)|].Max);

    tr[i].Min = min(tr[i<<].Min,tr[(i<<)|].Min);

}

void push_down(int i){

    if(tr[i].l == tr[i].r)return;

    if(tr[i].ne)

    {

        tr[i<<].Max = -tr[i<<].Max;

        tr[i<<].Min = -tr[i<<].Min;

        swap(tr[i<<].Min,tr[i<<].Max);

        tr[(i<<)|].Max = -tr[(i<<)|].Max;

        tr[(i<<)|].Min = -tr[(i<<)|].Min;

        swap(tr[(i<<)|].Max,tr[(i<<)|].Min);

        tr[i<<].ne ^= ;

        tr[(i<<)|].ne ^= ;

        tr[i].ne = ;

    }

}

void update(int i,int k,int val){ // 更新线段树的第k个值为val

    if(tr[i].l == k && tr[i].r == k)

    {

        tr[i].Max = val;

        tr[i].Min = val;

        tr[i].ne = ;

        return;

    }

    push_down(i);

    int mid = (tr[i].l + tr[i].r)/;

    if(k <= mid)update(i<<,k,val);

    else update((i<<)|,k,val);

    push_up(i);

}

void ne_update(int i,int l,int r){

    if(tr[i].l==l&&tr[i].r==r){

        tr[i].Max=-tr[i].Max;tr[i].Min=-tr[i].Min;

        swap(tr[i].Max,tr[i].Min);

        tr[i].ne^=;return;

    }

    push_down(i);

    int mid=(tr[i].l+tr[i].r)>>;

    if(r<=mid)ne_update(i<<,l,r);

    else if(l>mid)ne_update((i<<)|,l,r);

    else ne_update(i<<,l,mid),ne_update((i<<)|,mid+,r);

    tr[i].Min=min(tr[i<<].Min,tr[(i<<)|].Min);

    tr[i].Max=max(tr[i<<].Max,tr[(i<<)|].Max);

}

int query(int i,int l,int r){  //查询线段树中[l,r] 的最大值 

    if(tr[i].l == l && tr[i].r == r)

        return tr[i].Max;

    push_down(i);

    int mid = (tr[i].l + tr[i].r)/;

    if(r <= mid)return query(i<<,l,r);

    else if(l > mid)return query((i<<)|,l,r);

    else return max(query(i<<,l,mid),query((i<<)|,mid+,r));

    push_up(i);

}

int findmax(int u,int v){//查询u->v边的最大值

    int f1 = top[u], f2 = top[v];

    int tmp = -;

    while(f1 != f2)

    {

        if(deep[f1] < deep[f2])

        {

            swap(f1,f2);

            swap(u,v);

        }

        tmp = max(tmp,query(,p[f1],p[u]));

        u = fa[f1]; f1 = top[u];

    }

    if(u == v)return tmp;

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

    return max(tmp,query(,p[son[u]],p[v]));

}

void Negate(int u,int v){

    int f1=top[u],f2=top[v];

    while(f1!=f2){

        if(deep[f1]<deep[f2])swap(f1,f2),swap(u,v);

        ne_update(,p[f1],p[u]);

        u=fa[f1];f1=top[u];

    }

    if(u==v)return;

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

    ne_update(,p[son[u]],p[v]);

    return;

}

int E[MAXN][];

int main()

{

    //freopen("Cola.txt","r",stdin);

    freopen("maintaintree.in","r",stdin);

    freopen("maintaintree.out","w",stdout);

    int T,n;

    T=;

    while(T--){

        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][]);

        }

        dfs1(,,);

        dfs2(,);

        build(,,pos-);

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

            if(deep[E[i][]]>deep[E[i][]])swap(E[i][],E[i][]);

            update(,p[E[i][]],E[i][]);

        }

        char ch[];

        int u,v;

        while(){

            scanf("%s",ch);

            if(ch[]=='D')break;

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

            if(ch[]=='Q')printf("%d\n",findmax(u,v));

            else if(ch[]=='C')update(,p[E[u-][]],v);

            else Negate(u,v);

        }

    }

    return ;

}

巴特西

cogs1583. [POJ3237]树的维护