隐藏
「SDOI2011」消耗战 - 虚树+树形动规 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「SDOI2011」消耗战 - 虚树+树形动规

题目大意

    给出一棵$n$个结点的树,每条边有一个切断所付出的代价,有$m$次询问,每次询问给出一个点集$K$,要求将点集与$1$结点分离,回答最小代价。
$\quad\quad2\le n\le 250000,m\ge1,\sum K\le500000$


题目分析

询问和点的数量太多了,我们没有办法对每个询问作出$\log n$的回答。

因为每次给出了点集,且对点集总数量有限制,考虑使用虚树降低时间复杂度。

对询问的点集建立虚树,那么我们就可以对其做暴力的树形动规了。

设状态$f[i]$表示将$i$为根的子树完全与$1$分离所需的最小代价。
若$i$有一个儿子是给出的点集中的一个,那么$f[i]=Min[i]$,否则$f[i]=\min(Min[i],\sum f[son])$。

其中$Min[i]$表示$i$到根路径上的边权最小值。


代码

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=250005;

int n,m,step,a[maxn],First[maxn],Last[maxn],p[maxn][25],Depth[maxn];
LL f[maxn],Min[maxn];

bool cmp(int a,int b) {
return First[a]<First[b];
}

struct Edge {
int from,to,dist;
};

vector<Edge>edges[maxn];
vector<int>tree[maxn];

void AddEdge(int x,int y,int v) {
edges[x].push_back((Edge) {x,y,v});
}

void AddEdge(int x,int y) {
tree[x].push_back(y);
}

void Dfs(int Now,int fa,int depth) {
First[Now]=++step;
Depth[Now]=depth;
p[Now][0]=fa;
for(int i=1; i<=log2(depth); i++)
if(~p[Now][i-1])p[Now][i]=p[p[Now][i-1]][i-1];
else break;
for(Edge& e:edges[Now]) {
int Next=e.to;
if(Next==fa)continue;
Min[Next]=min(Min[Now],(LL)e.dist);
Dfs(Next,Now,depth+1);
}
Last[Now]=step;
}

int LCA(int a,int b) {
if(Depth[a]<Depth[b])swap(a,b);
int k=log2(Depth[a]);
for(int i=k; i>=0; i--) {
if(Depth[a]==Depth[b])break;
if(Depth[a]-(1<<i)>=Depth[b])a=p[a][i];
}
if(a==b)return b;
for(int i=k; i>=0; i--)
if(p[a][i]!=-1&&p[a][i]!=p[b][i]) {
a=p[a][i];
b=p[b][i];
}
return p[a][0];
}

void build(vector<int>& a) {
int tmp=a.size();
for(int i=0; i<tmp-1; i++)a.push_back(LCA(a[i],a[i+1]));
sort(a.begin(),a.end(),cmp);
auto it=unique(a.begin(),a.end());
a.erase(it,a.end());
static int top=0,S[maxn];
S[++top]=1;
for(int now:a) {
if(now==1)continue;
while(top>=1) {
if(First[now]>=First[S[top]]&&First[now]<=Last[S[top]]) {
AddEdge(S[top],now);
break;
}
top--;
}
if(S[top]!=now)S[++top]=now;
}
}

void TreeDp(int Now) {
f[Now]=Min[Now];
LL sum=0;
for(int Next:tree[Now]) {
TreeDp(Next);
sum+=f[Next];
}
if(!tree[Now].size())f[Now]=Min[Now]; //关键点只可能是叶子结点
else f[Now]=min(f[Now],sum);
tree[Now].clear(); //为下一次清空做准备
}

int main() {
memset(p,-1,sizeof(p));
n=Get_Int();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int(),v=Get_Int();
AddEdge(x,y,v);
AddEdge(y,x,v);
}
Min[1]=1e18;
Dfs(1,-1,1);
m=Get_Int();
for(int i=1; i<=m; i++) {
int k=Get_Int();
for(int j=1; j<=k; j++)a[j]=Get_Int();
sort(a+1,a+k+1,cmp);
vector<int>tmp;
tmp.clear();
tmp.push_back(a[1]);
for(int j=2; j<=k; j++) //题目性质:只保留靠上的点
if(!(First[a[j]]>=First[tmp.back()]&&First[a[j]]<=Last[tmp.back()]))tmp.push_back(a[j]);
build(tmp);
TreeDp(1);
printf("%lld\n",f[1]);
}
return 0;
}
姥爷们赏瓶冰阔落吧~