# BZOJ2286: [Sdoi2011]消耗战(虚树/树形DP)

Time Limit: 20 Sec  Memory Limit: 512 MB

Submit: 5246  Solved: 1978

[Submit][Status][Discuss]

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

12 32 22

## HINT

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

## Source

1.断开自己与父亲的联系，代价为从根到该节点的最小值

2.将子树内的节点全都处理掉的代价

```#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
#define LL long long
char buf[(1 << 21) + 1], *p1 = buf, *p2 = buf;
using namespace std;
const int MAXN = 250001;
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
char obuf[1 << 24], *O=obuf;
void print(LL x) {
if(x > 9) print(x / 10);
*O++= x % 10 + '0';
}
int N, M;
struct Edge {
int u, v, w, nxt;
}E[MAXN << 1];
inline void AddEdge(int x, int y, int z) {
E[num] = (Edge) {x, y, z, head[x]};
}
vector<int> v[MAXN];
void add_edge(int x, int y) {
v[x].push_back(y);
}
int a[MAXN], dfn[MAXN], topf[MAXN], siz[MAXN], son[MAXN], s[MAXN], top, deep[MAXN], fa[MAXN], ID = 0;
LL mn[MAXN];
void dfs1(int x, int _fa) {
siz[x] = 1; fa[x] = _fa;
for(int i = head[x]; i != -1; i = E[i].nxt) {
if(E[i].v == _fa) continue;
deep[E[i].v] = deep[x] + 1;
mn[E[i].v] = min(mn[x], (LL)E[i].w);
dfs1(E[i].v, x);
siz[x] += siz[E[i].v];
if(siz[E[i].v] > son[x]) son[x] = E[i].v;
}
}
void dfs2(int x, int topfa) {
topf[x] = topfa;
dfn[x] = ++ID;
if(!son[x]) return ;
dfs2(son[x], topfa);
for(int i = head[x]; i != -1; i = E[i].nxt)
if(!topf[E[i].v])
dfs2(E[i].v, E[i].v);
}
int LCA(int x, int y) {
while(topf[x] != topf[y]) {
if(deep[topf[x]] < deep[topf[y]]) swap(x, y);
x = fa[topf[x]];
}
if(deep[x] < deep[y]) swap(x, y);
return y;
}
void insert(int x) {
if(top == 1) {s[++top] = x; return ;}
int lca = LCA(x, s[top]);
if(lca == s[top]) return ;
while(top > 1 && dfn[s[top - 1]] >= dfn[lca]) add_edge(s[top - 1], s[top]), top--;
if(lca != s[top]) add_edge(lca, s[top]), s[top] = lca;//
s[++top] = x;
}
LL DP(int x) {
if(v[x].size() == 0) return mn[x];
LL sum = 0;
for(int i = 0; i < v[x].size(); i++)
sum += DP(v[x][i]);
v[x].clear();
return min(sum, (LL)mn[x]);
}
int comp(const int &a, const int &b) {
return dfn[a] < dfn[b];
}
int main() {
#ifdef WIN32
freopen("a.in", "r", stdin);
#endif
mn[1] = 1ll << 60;
for(int i = 1; i <= N - 1; i++) {
}
deep[1] = 1;
dfs1(1, 0);
dfs2(1, 1);
while(M--) {
for(int i = 1; i <= K; i++) a[i] = read();
sort(a + 1, a + K + 1, comp);
s[top = 1] = 1;
for(int i = 1; i <= K; i++) insert(a[i]);
while(top > 0)  add_edge(s[top - 1], s[top]), top--;
print(DP(1)), *O++ = '\n';
}
fwrite(obuf, O-obuf, 1 , stdout);
return 0;
}```

1811 篇文章120 人订阅

0 条评论