2286: [Sdoi2011消耗战
Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 2082 Solved: 736
[Submit][Status][Discuss]
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行，每行一个整数ki，代表第i次后，有ki个岛屿资源丰富，接下来k个整数h1,h2,…hk，表示资源丰富岛屿的编号。
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
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
32
22
HINT
对于100%的数据，2<=n<=250000,m>=1,sigma(ki)<=500000,1<=ki<=n-1
Source
虚树入门题，如果你想知道虚树如何构造：http://user.qzone.qq.com/872191552/main
DP
记dis[i]为点i到根节点的路径中最小的边的权值
f[i]=min(dis[i],sigma f[son[i]]);
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#define maxn 500100
#define llg long long
using namespace std;
struct node
{
llg df,po;
}d[maxn];
llg i,j,k,n,m,p[maxn][],dad[maxn],bj[maxn],dfs[maxn],cnt,T,deep[maxn],dis[maxn],se[maxn],q,ss[maxn],open,dl[maxn];
vector <llg> a[maxn],c[maxn],val[maxn];
stack <llg> z; inline int getint(){
char c=getchar(); llg w=,q=;
while(c!='-' && ( c<'' || c>'')) c=getchar();
if(c=='-') c=getchar(),q=;
while(c>='' && c<='') w=w*+c-'',c=getchar();
return q?-w:w;
} void link(llg x,llg y,llg z) {a[x].push_back(y); val[x].push_back(z); val[y].push_back(z); a[y].push_back(x);} void link_(llg x,llg y) {c[x].push_back(y); c[y].push_back(x);} bool cmp(const node&a,const node&b){return a.df<b.df;} void find_dad_deep(llg x,llg di)
{
bj[x]=; dfs[x]=++cnt; dis[x]=di;
llg w=a[x].size();
for (llg i=;i<w;i++)
if (!bj[a[x][i]])
{
dad[a[x][i]]=x; p[a[x][i]][]=x; deep[a[x][i]]=deep[x]+;
find_dad_deep(a[x][i],min(di,val[x][i]));
}
} void build_lca()
{
for (i=;(<<i)<=n;i++)
for (j=;j<=n;j++)
p[j][i]=p[p[j][i-]][i-];
} llg lca(llg x,llg y)
{
if (deep[x]<deep[y]) swap(x,y);
for (llg i=;i>=;i--) if (deep[p[x][i]]>=deep[y]) x=p[x][i];
if (x==y) return x;
for (llg i=;i>=;i--)
if (p[x][i]!=p[y][i]) {x=p[x][i]; y=p[y][i];}
return dad[x];
} llg st[maxn],top; void make_tree(llg x)
{
llg L=,g1,g2;
while(top)
{
g1=st[top];g2=st[top-];L=lca(g1,x);
if(deep[g2]>deep[L]) link_(g2,g1),top--;
else if(deep[g2]<deep[L]) {link_(g1,L);top--;break;}
else break;
}
if(st[top]!=L) st[++top]=L;
st[++top]=x;
} void ceshi()
{
for (llg i=;i<=n;i++)
{
llg w=c[i].size();
for (llg j=;j<w;j++) if (i<c[i][j]) cout<<i<<" "<<c[i][j]<<endl;
}
} llg dp(llg x)
{
bj[x]=;
dl[++open]=x;
llg w=c[x].size(),tot=;
for (llg i=;i<w;i++)
if (!bj[c[x][i]])
tot+=dp(c[x][i]);
if (ss[x]) return dis[x];
return min(tot,dis[x]);
} int main()
{
freopen("a.in","r",stdin); freopen("a.out","w",stdout);
cin>>n;
for (i=;i<n;i++)
{
llg x,y,z;
x=getint(),y=getint(),z=getint();
link(x,y,z);
}
deep[]=;
llg ggg=(llg)1e60;
find_dad_deep(,ggg); //dis[1]=0;
build_lca();
cin>>T; for (i=;i<=n;i++) bj[i]=;
while (T--)
{
m=getint();
llg x;
for (i=;i<=open;i++) {ss[se[i]]=; c[dl[i]].clear(); bj[dl[i]]=;}
q=,open=;
c[].clear(); bj[]=; ss[]=;
for (i=;i<=m;i++) {x=getint(); d[i].po=x; d[i].df=dfs[x]; q++; ss[x]=; se[q]=x; }
sort(d+,d+m+,cmp);
top=;
if (d[].po!=) st[++top]=;
for (i=;i<=m;i++) make_tree(d[i].po);
while(top!=) link_(st[top],st[top-]),top--;
//if (q<=0) printf("0\n"); else
printf("%lld\n",dp());
//ceshi();
//cout<<endl;
}
return ;
}