SPOJ2666. Query on a tree IV

7559 단어 query
SPOJ Problem Set (classical) 2666. Query on a tree IV Problem code: QTREE4
 
 
You are given a tree (an acyclic undirected connected graph) with N nodes, and nodes numbered 1,2,3...,N. Each edge has an integer value assigned to it(note that the value can be negative). Each node has a color, white or black. We define dist(a, b) as the sum of the value of the edges on the path from node a to node b.
All the nodes are white initially.
We will ask you to perfrom some instructions of the following form:
  • C a : change the color of node a.(from black to white or from white to black)
  • A : ask for the maximum dist(a, b), both of node a and node b must be white(a can be equal to b). Obviously, as long as there is a white node, the result will alway be non negative.

  • Input
  • In the first line there is an integer N (N <= 100000)
  • 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 value c (-1000 <= c <= 1000)
  • In the next line, there is an integer Q denotes the number of instructions (Q <= 100000)
  • In the next Q lines, each line contains an instruction "C a"or "A"

  • Output
    For each "A"operation, write one integer representing its result. If there is no white node in the tree, you should write "They have disappeared.".
    Example
    Input:
    
    3
    
    1 2 1
    
    1 3 1
    
    7
    
    A
    
    C 1
    
    A
    
    C 2
    
    A
    
    C 3
    
    A
    
    
    
    Output:
    
    2
    
    2
    
    0
    
    They have disappeared.
    --------------------------------------------------------
    : 。
    : 。 , , , , , 。
    /*
    
        :SPOJ2666. Query on a tree IV
    
        :  +  
    
        :    +     
    
              ,           ,                 
    
      ,    ,    。                       ,   
    
                ,              O(n) ,         
    
              ,                   6*N ,      
    
            ,          ,        pn[t],  t      
    
                 pn[t]+1,               :son[i]  i
    
             ,fa[i]  i           ,top[i]  i        ,
    
    siz[i]  i        ,cp[i]  i        ,cd[i]  i      
    
          ,csz[i]     i        ,pn[i]     i       ,
    
    cid[i]        t  (i-pn[t])         ,cnum    ,pnum  
    
       。
    
          ,              
    
    */
    
    
    
    #include <stdio.h>
    
    #include <string.h>
    
    #include <queue>
    
    #define clr(a,b) memset(a,b,sizeof(a))
    
    using namespace std;
    
    
    
    const int N=200005,M=7*N,inf=0x7fffffff;
    
    struct Node{
    
        int v,p;
    
        bool operator<(const Node & a)const{
    
            return v<a.v;
    
        }
    
        Node(int a,int b):v(a),p(b){}
    
    };
    
    int n,eid;
    
    int head[N],ed[N<<1],val[N<<1],nxt[N<<1];
    
    int son[N],fa[N],top[N],siz[N],dis[N],col[N];
    
    int cp[N],cd[N],csz[N],pn[N],cid[M],cnum,pnum;
    
    int le[M],ri[M],maxl[M],maxr[M],opt[M];
    
    priority_queue<Node>que[N],allque;
    
    
    
    void addedge(int s,int e,int v){
    
        ed[eid]=e;val[eid]=v;nxt[eid]=head[s];head[s]=eid++;
    
    }
    
    
    
    int pl(int a,int b){
    
        if(a==-inf||b==-inf)return -inf;
    
        return a+b;
    
    }
    
    
    
    void dfs_1(int s,int f){
    
        siz[s]=1;int maxx=0,p=-1;top[s]=s;fa[s]=f;
    
        for(int i=head[s];~i;i=nxt[i]){
    
            int e=ed[i];if(e==f){fa[s]=i;continue;}
    
            dfs_1(e,s);siz[s]+=siz[e];
    
            if(siz[e]>maxx){maxx=siz[e];p=i;}
    
        }
    
        son[s]=p;
    
    }
    
    
    
    void buildtree(int p,int rt,int l,int r){
    
        le[p+rt]=l;ri[p+rt]=r;int mid=(l+r)>>1;
    
        maxl[p+rt]=maxr[p+rt]=opt[p+rt]=-inf;
    
        if(l==r)return ;
    
        buildtree(p,rt<<1,l,mid);
    
        buildtree(p,rt<<1|1,mid+1,r);
    
    }
    
    
    
    void update(int p,int rt,int x){
    
        int l=le[p+rt],r=ri[p+rt],mid=(l+r)>>1;
    
        int root=p+rt,lroot=p+(rt<<1),rroot=p+(rt<<1|1);
    
        if(l==x&&r==x){
    
            int s=cid[p+x],d1=-inf,d2=-inf,p1=-1;
    
            while(!que[s].empty()){
    
                int v=que[s].top().v,ps=que[s].top().p;que[s].pop();
    
                int e=cid[ps];
    
                if(maxl[ps]+val[fa[e]]!=v)continue;
    
                p1=ps;d1=v;break;
    
            }
    
            while(!que[s].empty()){
    
                int v=que[s].top().v,ps=que[s].top().p,e=cid[ps];
    
                if(maxl[ps]+val[fa[e]]!=v||ps==p1){que[s].pop();continue;}
    
                d2=v;break;
    
            }
    
            if(~p1)que[s].push(Node(d1,p1));
    
            if(col[s])maxl[root]=maxr[root]=max(d1,0);
    
            else maxl[root]=maxr[root]=d1;
    
            if(col[s])opt[root]=max(d1,pl(d1,d2));
    
            else opt[root]=pl(d1,d2);
    
            if(col[s])opt[root]=max(opt[root],0);
    
            if(rt==1){
    
                if(~fa[s]){
    
                    int f=ed[fa[s]],v=val[fa[s]];
    
                    if(maxl[root]!=-inf)que[f].push(Node(maxl[root]+v,root));
    
                }
    
                if(opt[root]!=-inf)allque.push(Node(opt[root],root));
    
            }
    
            return ;
    
        }
    
        if(x<=mid)update(p,rt<<1,x);
    
        else update(p,rt<<1|1,x);
    
        int dm0=dis[cid[p+mid]],dm1=dis[cid[p+mid+1]];
    
        int dr=dis[cid[p+r]],dl=dis[cid[p+l]];
    
        maxl[root]=max(maxl[lroot],pl(dm1-dl,maxl[rroot]));
    
        maxr[root]=max(maxr[rroot],pl(dr-dm0,maxr[lroot]));
    
        opt[root]=max(opt[lroot],opt[rroot]);
    
        opt[root]=max(opt[root],pl(pl(maxl[rroot],maxr[lroot]),dm1-dm0));
    
        int s=cid[p+1];
    
        if(rt==1){
    
            if(~fa[s]){
    
                int f=ed[fa[s]],v=val[fa[s]];
    
                if(maxl[root]!=-inf)que[f].push(Node(maxl[root]+v,root));
    
            }
    
            if(opt[root]!=-inf)allque.push(Node(opt[root],root));
    
        }
    
    }
    
    
    
    void dfs_2(int s,int d,int c){
    
        if(s==top[s]){cp[s]=++cnum;csz[cp[s]]=0;}
    
        if(~son[s]){
    
            top[ed[son[s]]]=top[s];dfs_2(ed[son[s]],d+val[son[s]],c+1);
    
        }
    
        for(int i=head[s];~i;i=nxt[i])
    
            if(i!=son[s]&&i!=fa[s])dfs_2(ed[i],0,1);
    
        cp[s]=cp[top[s]];cd[s]=c;int k=cp[s];
    
        csz[k]=max(csz[k],cd[s]);dis[s]=d;
    
        if(s==top[s]){
    
            pn[k]=pnum;pnum+=6*csz[k];
    
            int t=s,num=2;cid[pn[k]+1]=s;
    
            while(~son[t]){
    
                cid[pn[k]+num]=ed[son[t]];
    
                t=ed[son[t]];num++;
    
            }
    
        }
    
    }
    
    
    
    void dfsinit(int s){
    
        col[s]=1;
    
        if(~son[s])dfsinit(ed[son[s]]);
    
        for(int i=head[s];~i;i=nxt[i])
    
            if(i!=fa[s]&&i!=son[s])dfsinit(ed[i]);
    
        update(pn[cp[s]],1,cd[s]);
    
    }
    
    
    
    int main(){
    
    //    freopen("/home/axorb/in","r",stdin);
    
    //    freopen("/home/axorb/out","w",stdout);
    
        scanf("%d",&n);eid=0;clr(head,-1);
    
        for(int i=1;i<n;i++){
    
            int a,b,c;scanf("%d%d%d",&a,&b,&c);
    
            addedge(a,b,c);addedge(b,a,c);
    
        }
    
        dfs_1(1,-1);cnum=pnum=0;dfs_2(1,0,1);clr(col,0);
    
        while(!allque.empty())allque.pop();
    
        for(int i=1;i<=cnum;i++){
    
            while(!que[i].empty())que[i].pop();buildtree(pn[i],1,1,csz[i]);
    
        }
    
        dfsinit(1);
    
    //    printf("%d
    ",allque.top().v); int q;scanf("%d",&q); while(q--){ char ss[20];scanf("%s",ss); if(ss[0]=='A'){ int flag=0; while(!allque.empty()){ int v=allque.top().v,p=allque.top().p; if(opt[p]!=v){allque.pop();continue;} printf("%d
    ",v);flag=1;break; } if(!flag)puts("They have disappeared."); } else{ int x;scanf("%d",&x);col[x]^=1; while(top[x]!=1){ update(pn[cp[x]],1,cd[x]);x=ed[fa[top[x]]]; } update(pn[cp[x]],1,cd[x]); } } }

    좋은 웹페이지 즐겨찾기