題意
給你n個節點的樹，讓你給每個節點進行賦值，并且賦的值需要為正整數；
同時當一個節點的值等于所有鄰居節點的值的和時，這個點為好點；
求出一組賦值情況，滿足樹的好點個數最大化的同時，所有節點賦值的總和最小；
思路
1. 顯然無法存在兩個好點相鄰存在的情況（除非只有兩個節點）；2. 對于壞點直接賦值為1即可；
3. 可以樹形dp解決，f[x][0/1][0/1]，第一維代表以x為根，第二維代表是否為好點，第三維代表是好點的個數/子樹節點值的總和
代碼
#include<bits/stdc++.h>
using namespace std;
vector<int> g[200005];
int f[200005][2][2];
long long ans[200005];
int cnt[200005];
void dp(int x, int fa) {
f[x][1][0] = 1;//好點個數
f[x][1][1] = g[x].size();//累計
f[x][0][0] = 0;
f[x][0][1] = 1;
for (auto k: g[x]) {
if (k == fa)continue;
dp(k, x);
}
for (auto k: g[x]) {
if (k == fa)continue;
f[x][1][0] += (f[k][0][0]);
f[x][1][1] += (f[k][0][1]);
}
for (auto k: g[x]) {
if (k == fa)continue;
if (f[k][0][0] > f[k][1][0]) {
f[x][0][0] += f[k][0][0];
f[x][0][1] += f[k][0][1];
} else if (f[k][0][0] == f[k][1][0]) {
f[x][0][0] += f[k][0][0];
f[x][0][1] += min(f[k][0][1], f[k][1][1]);
} else {
f[x][0][0] += f[k][1][0];
f[x][0][1] += f[k][1][1];
}
}
}
void down(int x, int fa, int now) {
ans[x] = now;
if (now == 1) {
for (auto k: g[x]) {
if (k == fa)continue;
down(k, x, 0);
}
} else {
for (auto k: g[x]) {
if (k == fa)continue;
if (f[k][0][0] > f[k][1][0]) {
down(k, x, 0);
} else if (f[k][0][0] == f[k][1][0]) {
if (f[k][0][1] < f[k][1][1])
down(k, x, 0);
else
down(k, x, 1);
} else {
down(k, x, 1);
}
}
}
}
void run() {
int n;
cin >> n;
// for (int i = 1; i <= n; i++)g[i].clear(), f[i] = 0, ans[i] = 0;
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
g[x].emplace_back(y);
g[y].emplace_back(x);
}
if (n == 2) {
cout << 2 << ' ' << 2 << '\n';
cout << 1 << ' ' << 1 << '\n';
return;
}
dp(1, 0);
bool flag = 1;
if (f[1][0][0] > f[1][1][0])flag = 0;
if (f[1][0][0] == f[1][1][0] && f[1][0][1] < f[1][1][1])flag = 0;
down(1, 0, flag);
cout << f[1][flag][0] << ' ' << f[1][flag][1] << '\n';
for (int i = 1; i <= n; i++) {
if (ans[i])cout << g[i].size() << ' ';
else cout << 1 << ' ';
}
}
int main() {
run();
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/536039.html
標籤：其他
上一篇：0經驗轉崗測驗經歷分享
下一篇：最小生成樹