BZOJ2286:[SDOI2011]消耗战(树形DP,虚树)

BZOJ2286:[SDOI2011]消耗战(树形DP,虚树)

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

HINT

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

Solution

虚树真是个好东西啊QAQ

推荐博客

建议对虚树的理解看第一个,构建看第二个QAQ

题解去看第二个吧我也懒得写了XD

顺带提一句因为本题特殊,所以建虚树的时候要写成57行那样,否则就把57行删掉改成58行就行了。

至于本题为什么要像57行那么写呢……

假设$x$点是$y$的祖先,如果$x$到根不连通,那么$y$到根一定不连通,所以$y$点也就没有加进去的必要了。而且加进去的话像我这样$DP$也就不对了啊啊QAQQQQ

Code

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<algorithm>
  5 #include<vector>
  6 #define N (250009)
  7 #define LL long long
  8 using namespace std;
  9 
 10 struct Edge{
   int to,next,len;}edge[N<<1];
 11 int n,m,k,u,v,l,dfs_num;
 12 int a[N],Depth[N],f[N][19],DFN[N];
 13 LL Min[N];
 14 int head[N],num_edge;
 15 
 16 void add(int u,int v,int l)
 17 {
 18     edge[++num_edge].to=v;
 19     edge[num_edge].next=head[u];
 20     edge[num_edge].len=l;
 21     head[u]=num_edge;
 22 }
 23 
 24 void DFS(int x,int fa)
 25 {
 26     f[x][0]=fa;
 27     for (int i=1; i<=18; ++i) f[x][i]=f[f[x][i-1]][i-1];
 28     DFN[x]=++dfs_num; Depth[x]=Depth[fa]+1;
 29     for (int i=head[x]; i; i=edge[i].next)
 30         if (edge[i].to!=fa)
 31         {
 32             Min[edge[i].to]=min(Min[x],(LL)edge[i].len);
 33             DFS(edge[i].to,x);
 34         }
 35 }
 36 
 37 int LCA(int x,int y)
 38 {
 39     if (Depth[x]<Depth[y]) swap(x,y);
 40     for (int i=18; i>=0; --i)
 41         if (Depth[f[x][i]]>=Depth[y]) x=f[x][i];
 42     if (x==y) return x;
 43     for (int i=18; i>=0; --i)
 44         if (f[x][i]!=f[y][i]) x=f[x][i], y=f[y][i];
 45     return f[x][0]; 
 46 }
 47 
 48 vector<int>E[N];
 49 void ADD(int x,int y) {E[x].push_back(y);}
 50 int stack[N],top;
 51 bool cmp(int x,int y) {
   return DFN[x]<DFN[y];}
 52 
 53 void Insert(int x)
 54 {
 55     if (top==1) {stack[++top]=x; return;}
 56     int lca=LCA(x,stack[top]);
 57     if (lca==stack[top]) return;
 58 //    if (lca==stack[top]) {stack[++top]=x; return;}
 59     while (top>1 && DFN[stack[top-1]]>=DFN[lca])
 60         ADD(stack[top-1],stack[top]), top--;
 61     if (lca!=stack[top]) ADD(lca,stack[top]), stack[top]=lca;
 62     stack[++top]=x;
 63 }
 64 
 65 void Build()
 66 {
 67     stack[top=1]=1;
 68     for (int i=1; i<=k; ++i) Insert(a[i]);
 69     while (top>=2) ADD(stack[top-1],stack[top]), top--;
 70 }
 71 
 72 LL DP(int x)
 73 {
 74     int sz=E[x].size();
 75     if (!sz) return Min[x];
 76     LL ans=0;
 77     for (int i=0; i<sz; ++i)
 78         ans+=DP(E[x][i]);
 79     E[x].clear();
 80     return min(ans,Min[x]);
 81 }
 82 
 83 int main()
 84 {
 85     Min[1]=1e18;
 86     scanf("%d",&n);
 87     for (int i=1; i<=n-1; ++i)
 88     {
 89         scanf("%d%d%d",&u,&v,&l);
 90         add(u,v,l); add(v,u,l);
 91     }
 92     DFS(1,0);
 93     scanf("%d",&m);
 94     for (int i=1; i<=m; ++i)
 95     {
 96         scanf("%d",&k);
 97         for (int j=1; j<=k; ++j) scanf("%d",&a[j]);
 98         sort(a+1,a+k+1,cmp);
 99         Build();
100         printf("%lld\n",DP(1));
101     }
102 }

转载于:https://www.cnblogs.com/refun/p/10064045.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/101285.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • centos安装python3

    centos安装python3centos安装python31、查看安装默认安装位置whereispython2、python2.7默认安装是在/usr/bin目录中,切换到/usr/bin/cd/usr/bin/3、安装相关的依赖包yuminstall-yepel-releasezlib-develbzip2-developenssl-develncurses-develsqlite-develreadline-develtk-develgccmake4、安装pipyuminsta

  • Mybatis常见面试题总结

    Mybatis常见面试题总结

  • MySQL comment_mysql和oracle的区别

    MySQL comment_mysql和oracle的区别iconv用法场景说明将UTF-8的编码转换成GBK编码,使用Notepad++创建一个UTF-8(无BOM)的编码文件,文件内容简单为风雨在途,保存文件名称为utf8.txt,转换之后存储文件名称为gbk.txt.1.1:iconv命令的使用iconv-fUTF8-tGBKgbk.txt1.2:iconv函数的使用#includesize_ticonv(iconv_tcd…

    2022年10月22日
  • 强大的自适应jQuery焦点图特效

    jQuery焦点图切换自适应效果自适应jQuery焦点图特效是一款支持移动端的响应式jQuery焦点图插件,支持flexible布局,支持移动触摸事件等。今天我们要来分享一款很灵活的jQuery焦点图

    2021年12月21日
  • PyTorch源码解读之torchvision.models「建议收藏」

    PyTorch源码解读之torchvision.models「建议收藏」PyTorch框架中有一个非常重要且好用的包:torchvision,该包主要由3个子包组成,分别是:torchvision.datasets、torchvision.models、torchvision.transforms。这3个子包的具体介绍可以参考官网:http://pytorch.org/docs/master/torchvision/index.html。具体代码可以参考github:

  • simHash 简介以及java实现[通俗易懂]

    simHash 简介以及java实现[通俗易懂] 传统的hash算法只负责将原始内容尽量均匀随机地映射为一个签名值,原理上相当于伪随机数产生算法。产生的两个签名,如果相等,说明原始内容在一定概率 下是相等的;如果不相等,除了说明原始内容不相等外,不再提供任何信息,因为即使原始内容只相差一个字节,所产生的签名也很可能差别极大。从这个意义上来 说,要设计一个hash算法,对相似的内容产生的签名也相近,是更为艰难的任务,因为它的签…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号