BZOJ3611: [Heoi2014]大工程 LCA单调性+树形dp

思路:思路基本同上一道题.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define INF 0x1f1f1f1f
 
namespace Fio{
    inline int getc(){
        static const int L=1<<15;static char buf[L],*S=buf,*T=buf;
        if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
        return*S++;
    }
    template<typename T>inline void Get(T&x){
        int c;while(!isdigit(c=getc()));x=c-'0';while(isdigit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
    }
}
#define N 1000010
int Head[N],Next[N<<1],End[N<<1],Len[N<<1];
inline void addedge(int a,int b,int x){static int q=1;End[q]=b,Next[q]=Head[a],Head[a]=q,Len[q++]=x;}
inline void make(int a,int b,int x){addedge(a,b,x),addedge(b,a,x);}
 
int dfn[N],id,dep[N],pa[N][21];
inline bool cmp(const int&x,const int&y){return dfn[x]<dfn[y];}
inline void dfs(int x,int fa){
    dfn[x]=++id;
    for(int j=Head[x];j;j=Next[j])if(End[j]!=fa)dep[End[j]]=dep[x]+1,pa[End[j]][0]=x,dfs(End[j],x);
}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=20;i>=0;--i)if(dep[pa[x][i]]>=dep[y])x=pa[x][i];
    if(x==y)return x;
    for(int i=20;i>=0;--i)if(pa[x][i]!=pa[y][i])x=pa[x][i],y=pa[y][i];
    return pa[x][0];
}
int getdis(int son,int Anc){
    //int r=0;for(int i=20;i>=0;--i)if(dep[pa[son][i]]>=dep[Anc])r+=w[son][i],son=pa[son][i];return r;
    return dep[son]-dep[Anc];
}
 
struct Array{
    int d[N],t[N],init;
    Array(){}
    Array(int _init):init(_init){}
    inline int ask(int x,int nowv){
        if(t[x]!=nowv)t[x]=nowv,d[x]=init;return d[x];
    }
    inline void modify(int x,int to,int nowv){
        t[x]=nowv,d[x]=to;
    }
    inline void maxi(int x,int to,int nowv){
        if(t[x]!=nowv)t[x]=nowv,d[x]=init;if(d[x]<to)d[x]=to;
    }
    inline void mini(int x,int to,int nowv){
        if(t[x]!=nowv)t[x]=nowv,d[x]=init;if(d[x]>to)d[x]=to;
    }
    inline void add(int x,int c,int nowv){
        if(t[x]!=nowv)t[x]=nowv,d[x]=init;d[x]+=c;
    }
};
 
int nowv;
struct Tree{
    Array h;int next[N],end[N],len[N],ind;
    inline void reset(){h.init=-1;ind=0;}
    inline void addedge(int a,int b){int q=ind++;end[q]=b,next[q]=h.ask(a,nowv),h.modify(a,q,nowv),len[q++]=getdis(b,a);}
}G;
 
int seq[N],siz,end;
 
int stk[N],top,Anc[N];
 
Array isimp(0),maxdep(-INF),mindep(INF),cnt(0);
long long tot;
int maxans,minans;
inline void mini(int&x,int y){if(x>y)x=y;}
inline void maxi(int&x,int y){if(x<y)x=y;}
void Solve(int x){
    for(int j=G.h.ask(x,nowv);j!=-1;j=G.next[j])Solve(G.end[j]),cnt.add(x,cnt.ask(G.end[j],nowv),nowv),tot+=(long long)G.len[j]*cnt.ask(G.end[j],nowv)*(siz-cnt.ask(G.end[j],nowv));
    if(isimp.ask(x,nowv))maxdep.modify(x,0,nowv),mindep.modify(x,0,nowv),cnt.add(x,1,nowv);
    for(int j=G.h.ask(x,nowv);j!=-1;j=G.next[j])
        mini(minans,mindep.ask(x,nowv)+mindep.ask(G.end[j],nowv)+G.len[j]),
        mindep.mini(x,mindep.ask(G.end[j],nowv)+G.len[j],nowv);
    for(int j=G.h.ask(x,nowv);j!=-1;j=G.next[j])
        maxi(maxans,maxdep.ask(x,nowv)+maxdep.ask(G.end[j],nowv)+G.len[j]),
        maxdep.maxi(x,maxdep.ask(G.end[j],nowv)+G.len[j],nowv);
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    //freopen("tt.out","w",stdout);
    #endif
    using namespace Fio;
    int n;Get(n);
    register int i,j;int a,b;for(i=1;i<n;++i)Get(a),Get(b),make(a,b,1);
    dep[1]=1,dfs(1,-1);
    for(j=1;j<=20;++j)
        for(i=1;i<=n;++i)pa[i][j]=pa[pa[i][j-1]][j-1];
    int Q;Get(Q);
    while(Q--){
        Get(siz);for(i=1;i<=siz;++i)Get(seq[i]);end=siz;sort(seq+1,seq+siz+1,cmp);
        ++nowv;for(i=1;i<=siz;++i)isimp.modify(seq[i],1,nowv);
        for(top=0,i=1;i<=siz;++i){
            if(!top)stk[++top]=seq[i];
            else{
                int Lca=lca(stk[top],seq[i]);Anc[seq[i]]=Lca;
                while(dep[stk[top]]>dep[Lca]){if(dep[stk[top-1]]<=dep[Lca])Anc[stk[top]]=Lca;--top;}
                if(Lca!=stk[top])Anc[Lca]=stk[top],seq[++end]=stk[++top]=Lca;
                stk[++top]=seq[i];
            }
        }
        sort(seq+1,seq+end+1,cmp);for(G.reset(),i=2;i<=end;++i)G.addedge(Anc[seq[i]],seq[i]);
        tot=0,minans=INF,maxans=-INF,Solve(seq[1]);
        printf("%lld %d %d\n",tot,minans,maxans);
    }
    return 0;
}