思路:思路基本同上一道题.
#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; }