Codeforces Round #300 E - Demiurges Play Again

E - Demiurges Play Again

感觉这种类型的dp以前没遇到过。。。 不是很好想。。

dp[u] 表示的是以u为子树进行游戏得到的值是第几大的。

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PII pair<int, int>
#define y1 skldjfskldjg
#define y2 skldfjsklejg using namespace std; const int N = 2e5 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ; int n, sum[N], dp[N], f[N], dp2[N];
vector<int> edge[N]; void dfs(int u, int fa) {
for(int v : edge[u]) {
if(v == fa) continue;
f[u] = true;
dfs(v, u);
sum[u] += sum[v];
}
sum[u] += !f[u];
} void dfs2(int u, int fa, int depth) {
if(!f[u]) {
dp[u] = ;
dp2[u] = ;
return;
}
if(depth & ) {
dp2[u] = inf;
for(int v : edge[u]) {
if(v == fa) continue;
dfs2(v, u, depth + );
dp[u] += dp[v];
dp2[u] = min(dp2[u], dp2[v]);
}
} else {
dp[u] = inf;
for(int v : edge[u]) {
if(v == fa) continue;
dfs2(v, u, depth + );
dp[u] = min(dp[u], dp[v]);
dp2[u] += dp2[v];
}
}
} int main() {
scanf("%d", &n);
for(int i = ; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
edge[u].push_back(v);
edge[v].push_back(u);
}
dfs(, );
dfs2(, , );
printf("%d %d\n", sum[] - dp[] + , dp2[]);
return ;
} /*
5
1 5 4 3 2
*/
上一篇:java 读取properties文件总结


下一篇:BZOJ 4034 [HAOI2015]T2(树链剖分)