1583. [POJ3237]树的维护

#include <stdio.h>#include <iostream>#include <algorithm>#include <cstring>using namespace std; const int MAXN = 100010;struct Edge{    int to,next;}edge[MAXN*2];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 = 0;    memset(head,-1,sizeof(head));    pos = 0;    memset(son,-1,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]=1;    for(int i=head[v];i!=-1;i=edge[i].next){        int to=edge[i].to;        if(to==u)continue;        dfs1(v,to,d+1);        num[v]+=num[to];        if(son[v]==-1||num[son[v]]<num[to])son[v]=to;    }}void dfs2(int u,int v){    top[u]=v;    p[u]=pos++;    if(son[u]==-1)return;    dfs2(son[u],v);    for(int i=head[u];i!=-1;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*3];void build(int i,int l,int r){    tr[i].l = l;    tr[i].r = r;    tr[i].Max = 0;    tr[i].Min = 0;    tr[i].ne = 0;    if(l == r)return;    int mid = (l+r)/2;    build(i<<1,l,mid);    build((i<<1)|1,mid+1,r);}void push_up(int i){    tr[i].Max = max(tr[i<<1].Max,tr[(i<<1)|1].Max);    tr[i].Min = min(tr[i<<1].Min,tr[(i<<1)|1].Min);}void push_down(int i){     if(tr[i].l == tr[i].r)return;    if(tr[i].ne)    {        tr[i<<1].Max = -tr[i<<1].Max;        tr[i<<1].Min = -tr[i<<1].Min;        swap(tr[i<<1].Min,tr[i<<1].Max);        tr[(i<<1)|1].Max = -tr[(i<<1)|1].Max;        tr[(i<<1)|1].Min = -tr[(i<<1)|1].Min;        swap(tr[(i<<1)|1].Max,tr[(i<<1)|1].Min);        tr[i<<1].ne ^= 1;        tr[(i<<1)|1].ne ^= 1;        tr[i].ne = 0;    }}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 = 0;        return;    }    push_down(i);    int mid = (tr[i].l + tr[i].r)/2;    if(k <= mid)update(i<<1,k,val);    else update((i<<1)|1,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^=1;return;    }    push_down(i);    int mid=(tr[i].l+tr[i].r)>>1;    if(r<=mid)ne_update(i<<1,l,r);    else if(l>mid)ne_update((i<<1)|1,l,r);    else ne_update(i<<1,l,mid),ne_update((i<<1)|1,mid+1,r);    tr[i].Min=min(tr[i<<1].Min,tr[(i<<1)|1].Min);    tr[i].Max=max(tr[i<<1].Max,tr[(i<<1)|1].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)/2;    if(r <= mid)return query(i<<1,l,r);    else if(l > mid)return query((i<<1)|1,l,r);    else return max(query(i<<1,l,mid),query((i<<1)|1,mid+1,r));    push_up(i);}int findmax(int u,int v){//查询u->v边的最大值     int f1 = top[u], f2 = top[v];    int tmp = -100000000;    while(f1 != f2)    {        if(deep[f1] < deep[f2])        {            swap(f1,f2);            swap(u,v);        }        tmp = max(tmp,query(1,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(1,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(1,p[f1],p[u]);        u=fa[f1];f1=top[u];    }    if(u==v)return;    if(deep[u]>deep[v])swap(u,v);    ne_update(1,p[son[u]],p[v]);    return;}int E[MAXN][3];int main(){    //freopen("Cola.txt","r",stdin);    freopen("maintaintree.in","r",stdin);    freopen("maintaintree.out","w",stdout);    int T,n;    T=1;    while(T--){        init();        scanf("%d",&n);        for(int i=0;i<n-1;i++){            scanf("%d%d%d",&E[i][0],&E[i][1],&E[i][2]);            addedge(E[i][0],E[i][1]);            addedge(E[i][1],E[i][0]);        }        dfs1(0,1,0);        dfs2(1,1);        build(1,0,pos-1);        for(int i=0;i<n-1;i++){            if(deep[E[i][0]]>deep[E[i][1]])swap(E[i][0],E[i][1]);            update(1,p[E[i][1]],E[i][2]);        }        char ch[10];        int u,v;        while(1){            scanf("%s",ch);            if(ch[0]==‘D‘)break;            scanf("%d%d",&u,&v);            if(ch[0]==‘Q‘)printf("%d\n",findmax(u,v));            else if(ch[0]==‘C‘)update(1,p[E[u-1][1]],v);            else Negate(u,v);        }    }    return 0;}