You are given a tree of?nn?vertices numbered from?11?to?nn. A tree is a connected undirected graph without cycles.

For each?i=1,2,…,ni=1,2,…,n, let?wiwi?be the weight of the?ii-th vertex. A vertex is called?good?if its weight is equal to the sum of the weights of all its neighbors.

Initially, the weights of all nodes are unassigned. Assign positive integer weights to each vertex of the tree, such that the number of good vertices in the tree is maximized. If there are multiple ways to do it, you have to find one that minimizes the sum of weights of all vertices in the tree.

Input

The first line contains one integer?nn?(2≤n≤2?1052≤n≤2?105) — the number of vertices in the tree.

Then,?n?1n?1?lines follow. Each of them contains two integers?uu?and?vv?(1≤u,v≤n1≤u,v≤n) denoting an edge between vertices?uu?and?vv. It is guaranteed that the edges form a tree.

Output

In the first line print two integers ?— the maximum number of good vertices and the minimum possible sum of weights for that maximum.

In the second line print?nn?integers?w1,w2,…,wnw1,w2,…,wn?(1≤wi≤1091≤wi≤109) ?— the corresponding weight assigned to each vertex. It can be proven that there exists an optimal solution satisfying these constraints.

If there are multiple optimal solutions, you may print any.

Examples

input

4 1 2 2 3 2 4

output

3 4 1 1 1 1

input

3 1 2 1 3

output

2 3 1 1 1

input

2 1 2

output

2 2 1 1

input

9 3 4 7 6 2 1 8 3 5 6 1 8 8 6 9 6

output

6 11 1 1 1 1 1 1 1 3 1

題意：?給出一顆樹，現在需要你為每個點分配權值，當一個點權值等于其相鄰點權值和，那么該點被稱為good點，求在滿足good點最大的前提下樹上所有點權和最小的方案。

分析：?首先需要想到相鄰兩點不可能同時被記為good點，這樣這道題目就有點像經典樹形dp題——沒有上司的舞會了，設狀態dp[i][0/1]表示在以i為根的子樹中且i點不是good點/i點是good點的最大總good點數，為了統計最終方案還需要記錄dp2[i][0/1]，dp2[i][0/1]表示在以i為根的子樹中且i點不是good點/i點是good點的總權重最小值。

接下來考慮狀態轉移，如果當前點是good點那么所有子節點都不能是good點，所以dp[now][1] += dp[son][0]，dp2[now][1] += dp2[son][0]，如果當前點不是good點那么子結點可以是good點也可以不是good點，具體哪種情況取決于dp值和dp2值，如果dp[son][0] > dp[son][1]，那么dp[now][0] += dp[son][0]，dp2[now][0] += dp2[son][0]，如果dp[son][0] <?dp[son][1]，那么dp[now][0] += dp[son][1]，dp2[now][0] += dp2[son][1]，如果dp[son][0] ==?dp[son][1]，此時dp[now][0]?+= dp[son][0]，畢竟都一樣大，加哪個都一樣，不過這時候dp2[now][0]就需要加小的那個了，在這種情況下如果dp2[son][0] <?dp2[son][1]，那么dp2[now][0] += dp2[son][0]，否則dp2[now][0] += dp2[son][1]。

狀態初始化就是對于葉子結點now，令dp[now][1] = 1, dp[now][0] = 0, dp2[now][1] = (點now相鄰點個數), dp2[now][0] = 0，然后先dfs到樹的最底層，回溯的過程中用子結點信息更新當前點信息。

求出dp數組和dp2數組后就可以開始構造方案了，這個過程其實和狀態轉移的思想類似。設一個布爾數組st[i][0/1]，st[i][0]表示在根節點不是good點的情況下i號點是否為good點，st[i][1]表示在根節點是good點的情況下i號點是否為good點。根據根節點是否為good點分為兩種情況，這兩種情況下的最優方案都需要求解。具體過程其實也是一個dfs，以根節點為good點這種情況舉例，此時先初始化st[1][1] = true，然后進入dfs，對于每個點都需要看其父節點的狀態，如果st[fa][1] == true，那么當前點狀態直接已知，肯定是st[now][1] = false，如果st[fa][1] = false，那么當前點可good也可不good，如果dp[now][1] > dp[now][0]，那么st[now][1]就應該取good點更優，st[now][1] = true，如果dp[now][1] <?dp[now][0]，那么st[now][1]不取good點更優，st[now][1] = false，如果dp[now][1] ==?dp[now][0]，再看dp2[now][1]和dp2[now][0]，如果dp2[now][1] <?dp2[now][0]，st[now][1] = true，否則st[now][1] = false，對于根節點不為good點的情況也是一樣的，只不過初始化st[1][0] = false。

最后特判一下n == 2的情況，因此此時不符合前面說的相鄰兩點間只有一個點能是good點。

具體代碼如下：

#include <iostream> #include <cstdio> #include <algorithm> #include <string> #include <cstring> #include <vector> #define int long long using namespace std;int dp[200005][2], s[2], dp2[200005][2]; bool st[200005][2]; vector<int> to[200005];void dfs(int now, int fa){for(int i = 0; i < to[now].size(); i++){int v = to[now][i];if(v == fa) continue;dfs(v, now);}dp[now][1] = 1, dp[now][0] = 0;dp2[now][1] = to[now].size(), dp2[now][0] = 0;int mx = 0;for(int i = 0; i < to[now].size(); i++){int v = to[now][i];if(v == fa) continue;if(dp[v][1] > dp[v][0]){mx += dp[v][1];dp2[now][0] += dp2[v][1];}else if(dp[v][0] > dp[v][1]){mx += dp[v][0];dp2[now][0] += dp2[v][0];}else{mx += dp[v][0];dp2[now][0] += min(dp2[v][0], dp2[v][1]);}dp[now][1] += dp[v][0];dp2[now][1] += dp2[v][0];}dp[now][0] += mx; }void dfs2(int now, int fa, int type){if(fa != 0){if(st[fa][type] == 1) st[now][type] = 0;else if(dp[now][0] > dp[now][1])st[now][type] = 0;else if(dp[now][1] > dp[now][0])st[now][type] = 1;else if(dp2[now][0] > dp2[now][1])st[now][type] = 1; elsest[now][type] = 0;}for(int i = 0; i < to[now].size(); i++){int v = to[now][i];if(v == fa) continue;dfs2(v, now, type);} }signed main() {int n;cin >> n;for(int i = 1; i < n; i++){int u, v;scanf("%lld%lld", &u, &v);to[u].push_back(v);to[v].push_back(u);}if(n == 2){puts("2 2\n1 1");return 0;}dfs(1, 0);printf("%lld ", max(dp[1][0], dp[1][1]));s[0] = s[1] = 0;//1無貢獻時權值和 st[1][0] = 0;dfs2(1, 0, 0);//1有貢獻時權值和st[1][1] = 1;dfs2(1, 0, 1);for(int i = 1; i <= n; i++){if(st[i][0]) s[0] += to[i].size();else s[0]++;}for(int i = 1; i <= n; i++){if(st[i][1]) s[1] += to[i].size();else s[1]++; }if(dp[1][0] > dp[1][1]){printf("%lld\n", s[0]);for(int i = 1; i <= n; i++){if(st[i][0]) printf("%lld ", to[i].size());else printf("1 ");}}else if(dp[1][0] < dp[1][1]){printf("%lld\n", s[1]);for(int i = 1; i <= n; i++){if(st[i][1]) printf("%lld ", to[i].size());else printf("1 ");}}else{printf("%lld\n", min(s[0], s[1]));if(s[0] < s[1]){for(int i = 1; i <= n; i++){if(st[i][0]) printf("%lld ", to[i].size());else printf("1 ");}}else{for(int i = 1; i <= n; i++){if(st[i][1]) printf("%lld ", to[i].size());else printf("1 "); }} }puts("");return 0; }

?

總結

以上是生活随笔為你收集整理的[树形dp]Weight the Tree Codeforces1646D的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。