+++++++++++++++++++++++++++++++++++++++++++

+本文作者:luyouqi233。               +

+欢迎访问我的博客:http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

http://www.lydsy.com/JudgeOnline/problem.php?id=2286

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

Sample Output

12
32
22

UPD 18/5/3:我终于懂虚树啦!以及美化代码。

显然是虚树啊……然而我还是不懂虚树怎么建的……

但是dp十分的简单,就是在虚树上dp[i]表示从i以下的资源节点都到不了i的最小费用。

设u为v的儿子,则:

当u有资源的时候,显然是从v到u的路径中挑一条最小费用的路径割掉即可。

当u没有资源的时候,要么将u往下的资源节点和u断开联系(即将dp[v]+=dp[u]),要么选择从v到u的路径中挑一条最小费用的路径割掉。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cctype>
#include<cstdio>
#include<cmath>
#include<stack>
using namespace std;
typedef long long ll;
const int N=,B=;
const int INF=0x7fffffff;
inline int read(){
int X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
struct node{
int w,to,nxt;
}e[*N];
int n,m,cnt,head[N],dep[N];
int anc[N][B+],val[N][B+];
int aux[N],pos[N],stk[N],tot;
int fa_aux[N],tmp[N],num,top;
bool vis[N];
ll dp[N];
inline bool cmp(int a,int b){return pos[a]<pos[b];}
inline void add(int u,int v,int w){
e[++cnt].to=v;e[cnt].w=w;e[cnt].nxt=head[u];head[u]=cnt;
}
void dfs(int u){
pos[u]=++tot;dep[u]=dep[anc[u][]]+;
for(int i=;i<=B;i++){
anc[u][i]=anc[anc[u][i-]][i-];
val[u][i]=min(val[u][i-],val[anc[u][i-]][i-]);
}
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to,w=e[i].w;
if(anc[u][]!=v){
anc[v][]=u;val[v][]=w;
dfs(v);
}
}
}
inline int LCA(int i,int j){
if(dep[i]<dep[j])swap(i,j);
for(int k=B;k>=;--k)
if(dep[anc[i][k]]>=dep[j])i=anc[i][k];
if(i==j)return i;
for(int k=B;k>=;--k)
if(anc[i][k]!=anc[j][k])
i=anc[i][k],j=anc[j][k];
return anc[i][];
}
void build(int t){
sort(aux+,aux+t+,cmp);
num=t;stk[top=]=;
for(int i=;i<=t;i++){
int u=aux[i];
if(!top)fa_aux[u]=,stk[++top]=u;
else{
int lca=LCA(u,stk[top]);
while(dep[stk[top]]>dep[lca]){
if(dep[stk[top-]]<=dep[lca])
fa_aux[stk[top]]=lca;
top--;
}
if(stk[top]!=lca){
fa_aux[lca]=stk[top];
stk[++top]=lca;
aux[++num]=lca;
}
fa_aux[u]=lca;
stk[++top]=u;
}
}
sort(aux+,aux+num+,cmp);
}
inline ll cut(int u,int v){
int res=INF;
for(int i=B;i>=;i--)
if(dep[anc[u][i]]>=dep[v]){
res=min(res,val[u][i]);
u=anc[u][i];
}
return res;
}
void solve(){
for(int i=;i<=num;i++)dp[aux[i]]=;
for(int i=num;i>=;i--){
int u=aux[i],v=fa_aux[u];
if(!vis[u])
dp[v]+=min(dp[u],cut(u,v));
else dp[v]+=cut(u,v);
}
}
int main(){
n=read();
for(int i=;i<n;i++){
int u=read(),v=read(),w=read();
add(u,v,w);add(v,u,w);
}
dfs();
m=read();
while(m--){
int t=read();
for(int i=;i<=t;i++){
int u=read();
aux[i]=tmp[i]=u;vis[u]=;
}
aux[++t]=;
build(t);solve();
printf("%lld\n",dp[]);
for(int i=;i<=t;i++)vis[tmp[i]]=;
}
}

最新文章

  1. Android Soap实例
  2. 在CentOS上装 ElasticSearch
  3. Oracle 11g R2 常用配置与日志的文件位置
  4. Android短信监听软件
  5. 打造自己的程序员品牌(摘自Infoq)
  6. 常用jQuery选择器总结【转】
  7. Android ble 蓝牙4.0 总结
  8. CentOS7安装GitLab、汉化及使用
  9. JAXB(Java Architecture for XML Binding)
  10. 从Android源码修改cpu信息
  11. [dev] EPOLLOUT的应用场景
  12. Daily Scrum - 11/24
  13. .hivehistory
  14. 商业规则引擎IBM WebSphere ILog JRules概述,开发基础教程
  15. linux系统socket通信编程2
  16. 转!idea启动后发现tomcat前面出现红色或是灰色的问号
  17. Hive入门学习随笔(一)
  18. 1、设备网络SDK主要功能
  19. Java - 多线程与锁
  20. iOS的内存分配

热门文章

  1. VIM第七版
  2. Android性能优化来龙去脉总结
  3. 第五模块&#183;WEB开发基础-第3章jQuery&amp;Bootstrap
  4. Python 默认参数值
  5. openjudge-2的100次方阶乘
  6. [JSON].exists( keyPath )
  7. git push origin master 错误解决办法
  8. vue watch监控对象
  9. UVa 1586 - Molar Mass - ACM/ICPC Seoul 2007 - C语言
  10. chameleon-Mini(迷你变色龙)