【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=2286

【题目大意】

  出一棵边权树,每次给出一些关键点,求最小边割集,
  使得1点与各个关键点不相连

【题解】

  我们将所有关键点抽出构建虚树,记录每个点到根的最小边权,
  在虚树上标记关键点,在虚树上做树形dp,
  对于虚树上所有点,要么切断所有向下的路径,要么切断向上的路径,
  对于被标记的关键点,一定是切断向上路径。

【代码】

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N=250010;
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
namespace Virtual_Tree{
const LL INF=1LL<<60;
LL mn[N];
int ed,d[N],vis[N],f[N],size[N],son[N],w[N<<1];
int nxt[N<<1],g[N],v[N<<1],st[N],en[N],dfn,top[N];
void add_edge(int x,int y,int z){v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;}
void dfs(int x){
size[x]=1;
for(int i=g[x];i;i=nxt[i])if(v[i]!=f[x]){
mn[v[i]]=min(mn[x],(LL)w[i]);
f[v[i]]=x,d[v[i]]=d[x]+1;
dfs(v[i]),size[x]+=size[v[i]];
if(size[v[i]]>size[son[x]])son[x]=v[i];
}
}
void dfs2(int x,int y){
if(x==-1)return;
st[x]=++dfn;top[x]=y;
if(son[x])dfs2(son[x],y);
for(int i=g[x];i;i=nxt[i])if(v[i]!=son[x]&&v[i]!=f[x])dfs2(v[i],v[i]);
en[x]=dfn;
}
int lca(int x,int y){
for(;top[x]!=top[y];x=f[top[x]])if(d[top[x]]<d[top[y]]){int z=x;x=y;y=z;}
return d[x]<d[y]?x:y;
}
void Initialize(){
mn[1]=INF;
memset(g,dfn=ed=0,sizeof(g));
memset(v,0,sizeof(v));
memset(nxt,0,sizeof(nxt));
memset(son,-1,sizeof(son));
}
int V[N<<1],NXT[N<<1],G[N],ED,a[N],q[N],mark[N];
void ADD_edge(int x,int y){V[++ED]=y;NXT[ED]=G[x];G[x]=ED;}
bool cmp(int a,int b){return st[a]<st[b];}
LL dp[N];
void DP(int x){
dp[x]=mn[x];
LL tmp=0;
for(int i=G[x];i;i=NXT[i]){
DP(V[i]);
if(mark[V[i]])tmp+=mn[V[i]];
else tmp+=dp[V[i]];
}G[x]=0;
if(tmp==0)dp[x]=mn[x];
else if(tmp<=dp[x])dp[x]=tmp;
}
void build(int m){
int tot,t,i,x; ED=0;
vis[1]=a[1]=1;
for(tot=++m,i=2;i<=m;i++)a[i]=read(),mark[a[i]]=vis[a[i]]=1;
sort(a+1,a+m+1,cmp);
for(i=1;i<m;i++)if(!vis[x=lca(a[i],a[i+1])])vis[a[++tot]=x]=1;
m=tot,sort(a+1,a+m+1,cmp);
for(q[t=1]=1,i=2;i<=m;q[++t]=a[i++]){
while(st[a[i]]<st[q[t]]||en[a[i]]>en[q[t]])t--;
ADD_edge(q[t],a[i]);
}DP(1);
for(i=1;i<=m;i++)mark[a[i]]=vis[a[i]]=0;
}
}
using namespace Virtual_Tree;
int n,m,k;
int main(){
scanf("%d",&n);
Initialize();
for(int i=1;i<n;i++){
int u,v,w;
u=read();v=read();w=read();
add_edge(u,v,w);
add_edge(v,u,w);
}dfs(1); dfs2(1,1);
scanf("%d",&m);
while(m--){
scanf("%d",&k);
build(k);
printf("%lld\n",dp[1]);
}return 0;
}

最新文章

  1. js 10秒倒计时 功能
  2. asp.net+swfupload 多图片批量上传(附源码下载)
  3. JavaScript 三种绑定事件方式之间的区别
  4. Andriod手势密码破解
  5. 《Learn python the hard way》Exercise 48: Advanced User Input
  6. C++输出中文字符(转)
  7. delphi关于文件操作集锦
  8. robotframework在3.7下的搭建
  9. C#获取文件夹下面的所有文件名
  10. python程序正式开始
  11. 推荐一个php7+ mongodb三方类
  12. Java单例模式《一》饿汉式
  13. 汇编 ADD指令
  14. Apache+wsgi+flask部署
  15. jmeter压测前清理内存
  16. 在Windows下使用svn命令行教程及svn命令行的解释
  17. VC++获取一个GB级大文件的字节大小
  18. 【读书笔记】《HTTP权威指南》:Web Robots
  19. HDU2571:命运(简单dp)
  20. Java多线程系列 基础篇01 线程的状态

热门文章

  1. C# 类内部添加索引器
  2. 一些达成共识的JavaScript编码风格约定【转】
  3. URI设计原则
  4. ie8下trim失效
  5. [Leetcode Week17]Copy List with Random Pointer
  6. HDU 6109 数据分割 并查集,SET
  7. 设计模式之笔记--适配器模式(Adapter)
  8. 数据类型转换(计算mac地址)
  9. django使用用户名或手机号码登录
  10. 《逐梦旅程 WINDOWS游戏编程之从零开始》笔记6——四大变换&amp;光照与材质