bzoj 2286 [Sdoi2011]消耗战

bzoj 2286 [Sdoi2011]消耗战

​​ 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

Source

Stage2 day2

求切断k个位置到1的路径上的最小值 那么有个显然的o(n) dp方法 但是总复杂度是n*m不可接受 那么这中间有很多废点 他们并没有用 但是却需要消耗时间复杂度 就考虑将他们呢缩点然后就建出了虚树 虚树包含所有有效点的lca 和所有的有效点 那么建出虚树之后再dp复杂度就恰好可以

那怎么建虚树考虑新来一个节点 lca如果我lca的dep比栈中的点的深度要小 那么栈中的点需要互相连边 建出虚树即可 然后都处理之后再将lca连进去即可 注意这题 初始情况就需要一个long long的才可以

#include#include#include#include#define ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=1000010;struct node{ int y,next,z;}data1[N>>1],data[N];int q[N],top,h1[N>>2],h[N>>1],in[N>>2],out[N>>2],num;ll dp[N];int fa[N>>2][20],dis[N>>2],Log[N>>2],pd[N>>1],m,n,dep[N>>1];inline void dfs(int x){ in[x]=++num; for (int i=h1[x];i;i=data1[i].next){ int y=data1[i].y,z=data1[i].z;if (y==fa[x][0]) continue; dep[y]=dep[x]+1;dis[y]=min(dis[x],data1[i].z);fa[y][0]=x; for (int j=1;j<=Log[dep[y]];++j) fa[y][j]=fa[fa[y][j-1]][j-1];dfs(y); }out[x]=num;}inline int lca(int x,int y){ if(dep[x]=in[y];}inline void insert1(int x,int y,int z){ data[++num].y=y;data[num].next=h[x];data[num].z=z;h[x]=num;}inline void gao(int x,ll w){ dp[x]=0; for (int i=h[x];i;i=data[i].next){ int y=data[i].y;gao(y,data[i].z);dp[x]+=dp[y]; }if (!h[x]) dp[x]=w;dp[x]=min(dp[x],w);h[x]=0;}inline void solve(){ static int K;K=read();int k=1; for (int i=1;i<=K;++i) pd[i]=read();sort(pd+1,pd+K+1,cmp); for (int i=2;i<=K;++i) if (!check(pd[k],pd[i]))pd[++k]=pd[i]; q[top=1]=1;num=0; for (int i=1;i<=k;++i){ int t=lca(q[top],pd[i]); while(top>1){ if (dep[t]>=dep[q[top-1]]){ if (t!=q[top]) insert1(t,q[top],dis[q[top]]);--top; if (q[top]!=t) q[++top]=t;break; } insert1(q[top-1],q[top],dis[q[top]]);--top; }if (pd[i]!=q[top]) q[++top]=pd[i]; }int lt=q[1]; for (int i=2;i<=top;++i) insert1(lt,q[i],dis[q[i]]),lt=q[i];gao(1,(1LL<<60));printf("%lld\n",dp[1]);}int main(){ freopen("bzoj2286.in","r",stdin); n=read();Log[0]=-1;dis[1]=0x3f3f3f3f; for (int i=1;i<=n;++i) Log[i]=Log[i>>1]+1; for (int i=1;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。