虚树+树形DP

  1 /**************************************************************  2     Problem: 2286  3     User: Tunix  4     Language: C++  5     Result: Accepted  6     Time:6616 ms  7     Memory:60120 kb  8 ****************************************************************/  9   10 //BZOJ 2286 11 #include<cstdio> 12 #include<cstring> 13 #include<cstdlib> 14 #include<iostream> 15 #include<algorithm> 16 #define rep(i,n) for(int i=0;i<n;++i) 17 #define F(i,j,n) for(int i=j;i<=n;++i) 18 #define D(i,j,n) for(int i=j;i>=n;--i) 19 using namespace std; 20 inline int getint(){ 21     int v=0,sign=1; char ch=getchar(); 22     while(ch<‘0‘||ch>‘9‘){ if (ch==‘-‘) sign=-1; ch=getchar();} 23     while(ch>=‘0‘&&ch<=‘9‘){ v=v*10+ch-‘0‘; ch=getchar();} 24     return v*=sign; 25 } 26 /******************tamplate*********************/ 27 const int N=250010; 28 const long long INF=100000000000LL; 29 typedef long long LL; 30 int n,m,dfn[N],dfs_clock=0,dep[N],fa[N][20],g[N][20],a[N]; 31 LL dp[N]; 32 bool v[N];//标记资源点 33   34 inline int LCA(int x,int y){ 35     if (dep[x]<dep[y]) swap(x,y); 36     int t=dep[x]-dep[y]; 37     F(i,0,18) if(t&(1<<i)) x=fa[x][i]; 38     if(x==y) return x; 39     D(i,18,0) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; 40     return fa[x][0]; 41 } 42 inline int dist(int x,int y){ 43     int t=dep[x]-dep[y],ans=1000000000; 44     D(i,18,0) if(t&(1<<i)) ans=min(ans,g[x][i]),x=fa[x][i]; 45     return ans; 46 } 47   48 struct graph{ 49     int head[N],to[N<<1],next[N<<1],len[N<<1],cnt; 50     void add(int x,int y,int l){ 51         to[++cnt]=y; next[cnt]=head[x]; head[x]=cnt;len[cnt]=l; 52         to[++cnt]=x; next[cnt]=head[y]; head[y]=cnt;len[cnt]=l; 53     } 54     void add(int x,int y){ 55         to[++cnt]=y; next[cnt]=head[x]; head[x]=cnt; 56     } 57     void dfs(int x){ 58         dfn[x]=++dfs_clock; 59         F(i,1,18) 60             if(dep[x]>=(1<<i)){ 61                 fa[x][i]=fa[fa[x][i-1]][i-1]; 62                 g[x][i]=min(g[x][i-1],g[fa[x][i-1]][i-1]); 63             } 64             else break; 65         for(int i=head[x];i;i=next[i]) 66             if(to[i]!=fa[x][0]){ 67                 fa[to[i]][0]=x; 68                 g[to[i]][0]=len[i]; 69                 dep[to[i]]=dep[x]+1; 70                 dfs(to[i]); 71             } 72     } 73     void dfs(int x,int f){ 74         //dp[x]表示使x到不了任何一个后代的资源点的最小费用 75         dp[x]=0; 76         for(int i=head[x];i;i=next[i]) 77             if(to[i]!=f){ 78                 dfs(to[i],x); 79                 dp[x]+=min(v[to[i]] ? INF : dp[to[i]],(LL)dist(to[i],x)); 80                 //如果这个子节点是能源点，则必须砍这条边 81             } 82         head[x]=0; 83         //清空，为下个询问做预处理，反正每个节点只会访问一次…… 84     } 85 }G1,G2; 86 inline bool cmp(int a,int b){ return dfn[a]<dfn[b]; } 87 int st[N],top=0; 88 int main(){ 89     n=getint(); 90     int x,y,z; 91     F(i,2,n){ 92         x=getint(); y=getint(); z=getint(); 93         G1.add(x,y,z); 94     } 95     dep[1]=1; 96     G1.dfs(1); 97     int T=getint(); 98     while(T--){ 99         m=getint();100         F(i,1,m) {a[i]=getint(); v[a[i]]=1;}101         sort(a+1,a+m+1,cmp);102         //栈维护建虚树103         st[top=1]=1; G2.cnt=0;104         F(i,1,m){105             int x=a[i],f=LCA(x,st[top]);106             while(dep[f]<dep[st[top]]){107                 if(dep[f]>=dep[st[top-1]]){108                     G2.add(f,st[top--]);109                     if (st[top]!=f) st[++top]=f;110                     break;111                 }112                 G2.add(st[top-1],st[top]);top--;113             }114             if(st[top]!=x) st[++top]=x;115         }116         while(--top) G2.add(st[top],st[top+1]);117         G2.dfs(1,0);118         printf("%lld\n",dp[1]);119         F(i,1,m) v[a[i]]=0;120     }121     return 0;122 }