【bzoj2286】消耗战

  • 本文为博主原创,未经许可不得转载
  • 虚树系列第一题

首先考虑一般的做法:

设$f[x]$表示以$x$为根子树中所有资源点不能到达根的最小代价,$minn[x]$表示$x$到根路径上的最小边权

那么显然有:$f[x]=min(minn[x],\sum y) $  ($y$是$x$的儿子)

然后我们发现所有的$K$之和不超过$500000$,那么做法就很显然了:

每次把所有的资源点拿出了建一颗虚树,然后在虚树上$dp$就可以了

需要注意的是:建虚树时只用考虑离根最近的关键点,也就是说如果关键点$x$在关键点$y$的子树中,那么$x$可以忽略

这是因为如果$y$是关键点,那么$y$到$root$的路径上不然会切掉一条边,这时$x,z$到$root$就不通了

而且如果不忽略的话,答案会出错(考虑$dp$转移的过程就知道为什么会出错了

另外:这题需要用$longlong$(被坑了好久

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>
#define MAXN 250010
#define FILE "read"
#define cmin(a,b) a=min(a,b)
#define cmax(a,b) a=max(a,b)
using namespace std;
typedef long long ll;
const ll INF=1e18;
struct node{int y,next;ll v;}e[MAXN<<1];
int n,m,len,dfs_clock,Link[MAXN],dfn[MAXN],deep[MAXN],h[MAXN],sta[MAXN],anc[MAXN][25];
ll minn[MAXN],f[MAXN];
inline int read(){
int x=0,f=1; char ch=getchar();
while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
bool mycmp(int x,int y){return dfn[x]<dfn[y];}
void insert(int x,int y,int v){
e[++len].next=Link[x];Link[x]=len;e[len].y=y;e[len].v=v;
e[++len].next=Link[y];Link[y]=len;e[len].y=x;e[len].v=v;
}
void Insert(int x,int y){
if(x==y) return;
e[++len].next=Link[x];Link[x]=len;e[len].y=y;
}
void dfs(int x,int fa){
dfn[x]=++dfs_clock; anc[x][0]=fa;
for(int i=1;i<=20;++i) anc[x][i]=anc[anc[x][i-1]][i-1];
for(int i=Link[x];i;i=e[i].next)if(e[i].y!=fa){
minn[e[i].y]=min(minn[x],e[i].v);
deep[e[i].y]=deep[x]+1;
dfs(e[i].y,x);
}
}
int LCA(int x,int y){
if(deep[x]<deep[y]) swap(x,y);
for(int i=20;i>=0;--i) if(deep[anc[x][i]]>=deep[y]) x=anc[x][i];
if(x==y) return x;
for(int i=20;i>=0;--i) if(anc[x][i]!=anc[y][i]) x=anc[x][i],y=anc[y][i];
return anc[x][0];
}
void dp(int x){
ll ret=0; f[x]=minn[x];
for(int i=Link[x];i;i=e[i].next){
dp(e[i].y);
ret+=f[e[i].y];
}Link[x]=0;
if(ret) cmin(f[x],ret);
}
void solve(){
int K=read(),top=0; len=0;
for(int i=1;i<=K;++i) h[i]=read();
sort(h+1,h+K+1,mycmp);
int tot=0; h[++tot]=h[1];
for(int i=2;i<=K;i++) if(LCA(h[tot],h[i])!=h[tot])h[++tot]=h[i];//精妙的操作
sta[++top]=1;
for(int i=1;i<=tot;++i){
int x=h[i],lca=LCA(x,sta[top]);
if(lca==sta[top]) sta[++top]=x;
else{
while(top>=1&&deep[sta[top-1]]>=deep[lca])
Insert(sta[top-1],sta[top]),--top;
if(sta[top]!=lca){
Insert(lca,sta[top--]);
sta[++top]=lca;
}
sta[++top]=x;
}
}
for(int i=1;i<top;++i) Insert(sta[i],sta[i+1]);
dp(1); printf("%lld\n",f[1]);
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
n=read(); deep[1]=1; minn[1]=INF;
for(int i=1;i<n;++i){
int x=read(),y=read(),v=read();
insert(x,y,v);
}
dfs(1,0); m=read();
memset(Link,0,sizeof(Link));
for(int i=1;i<=m;++i) solve();
printf("%d\n",clock());
return 0;
}
文章目录
,