消耗战

Time Limit: 20 Sec  Memory Limit: 512 MB

[][][]

Description

　　在一场战争中，战场由n个岛屿和n-1个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为1的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他k个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望在满足目标的同时使得总代价最小。

　　侦查部门还发现，敌军有一台神秘机器。即使我军切断所有能源之后，他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁，而且会重新随机资源分布（但可以保证的是，资源不会分布到1号岛屿上）。不过侦查部门还发现了这台机器只能够使用m次，所以我们只需要把每次任务完成即可。

Input

　　第一行一个整数n，代表岛屿数量。

　　接下来n-1行，每行三个整数u,v,w，代表u号岛屿和v号岛屿由一条代价为c的桥梁直接相连，保证1<=u,v<=n且1<=c<=100000。

　　第n+1行，一个整数m，代表敌方机器能使用的次数。

　　接下来m行，每行一个整数k_i，代表第i次后，有k_i个岛屿资源丰富，接下来k个整数h₁,h₂,…h_k，表示资源丰富岛屿的编号。

Output

　　输出有m行，分别代表每次任务的最小代价。

Sample Input

　　10

　　1 5 13

　　1 9 6

　　2 1 19

　　2 4 8

　　2 3 91

　　5 6 8

　　7 5 4

　　7 8 31

　　10 7 9

　　3

　　2 10 6

　　4 5 7 8 3

　　3 9 4 6

Sample Output

　　12

　　32

　　22

HINT

 　　对于100%的数据，2<=n<=250000,m>=1,sigma(ki)<=500000,1<=ki<=n-1

Main idea

　　给定一棵带权树，每次询问给出若干个关键节点，求出删去若干边使得关键节点无法到达根的最优方案。

Solution

　　显然想到了树形DP，但是直接做DP会TLE。

　　我们又发现了其实没有必要把全部边都走完，那么只要构建一棵虚树，在虚树上跑DP即可。

　　虚树构建方法： 

　　1. 将关键点按照DFS序排序；

　　2. 求出排序后相邻两点的LCA（可以证明就是任意两点的LCA），和关键点一起按照DFS序排序，去重后得到虚树点集；

　　3. 用栈扫描一遍，维护从根到当前点的链（方法：如果栈顶是i的祖先，那么连边，加入i，否则弹栈）。

Code

1 #include
      
           2 #include
       
            3 #include
        
             4 #include
         
              5 #include
          
               6 #include
           
             7 #include
            
              8 using namespace std; 9 10 const int ONE=500001; 11 const int INF=2147483640; 12 13 int n,m,T; 14 int x,y,z; 15 int next1[ONE],first1[ONE],go1[ONE],w1[ONE],tot1; 16 int next[ONE],first[ONE],go[ONE],w[ONE],tot; 17 int size[250001],Rank[250001]; 18 int dfn[250001],cnt,num; 19 int f[ONE][25],Dep[250001]; 20 int Output[ONE]; 21 int N; 22 long long dp[250001]; 23 int Minedge[ONE]; 24 int vis[250001]; 25 int q[250001],top; 26 27 struct power 28 { 29 int v; 30 int rank; 31 }a[ONE]; 32 33 int cmp(const power &a,const power &b) 34 { 35 return a.rank
             
              57) 47 if(c=='-')Q=-1; 48 if(Q) res=c-48; 49 while((c=getchar())>=48 && c<=57) 50 res=res*10+c-48; 51 return res*Q; 52 } 53 54 int Add(int u,int v,int z) 55 { 56 next1[++tot1]=first1[u]; first1[u]=tot1; go1[tot1]=v; w1[tot1]=z; 57 next1[++tot1]=first1[v]; first1[v]=tot1; go1[tot1]=u; w1[tot1]=z; 58 } 59 60 int New_Add(int u,int v,int z) 61 { 62 next[++tot]=first[u]; first[u]=tot; go[tot]=v; w[tot]=z; 63 next[++tot]=first[v]; first[v]=tot; go[tot]=u; w[tot]=z; 64 } 65 66 int Dfs(int u,int father) 67 { 68 dfn[++cnt]=u; 69 size[u]=1; 70 Dep[u]=Dep[father]+1; 71 for(int i=0;i<=19;i++) 72 { 73 f[u][i+1]=f[f[u][i]][i]; 74 } 75 76 for(int e=first1[u];e;e=next1[e]) 77 { 78 int v=go1[e]; 79 if(v==father) continue; 80 f[v][0]=u; 81 Minedge[v]=min(w1[e],Minedge[u]); 82 Dfs(v,u); 83 size[u]+=size[v]; 84 } 85 } 86 87 int LCA(int x,int y) 88 { 89 if(Dep[x]
              
               =0;i--) 91 { 92 if(Dep[f[x][i]]>=Dep[y]) x=f[x][i]; 93 if(x==y) return x; 94 } 95 96 for(int i=20;i>=0;i--) 97 { 98 if(f[x][i]!=f[y][i]) 99 {100 x=f[x][i];101 y=f[y][i];102 }103 }104 105 return f[x][0];106 }107 108 int Check(int u,int v)109 {110 if(Rank[u]<=Rank[v] && Rank[v]<=Rank[u]+size[u]-1) return 1; 111 return 0;112 }113 114 void Deal()115 {116 tot=0;117 for(int i=2;i<=num;i++)118 {119 int x=a[i].v;120 while(!Check(q[top],x)) top--;121 New_Add(q[top],x,Minedge[x]);122 q[++top]=x;123 }124 }125 126 void Tree_dp(int u,int father)127 {128 dp[u]=0;129 for(int e=first[u];e;e=next[e])130 {131 int v=go[e];132 if(v==father) continue;133 Tree_dp(v,u);134 if(vis[v]) dp[u]+=w[e];135 else dp[u]+=min(dp[v],(long long)w[e]);136 }137 first[u]=0;138 }139 140 int main()141 { 142 n=get();143 for(int i=1;i