WeighttheTree（树形dp）

题目Link
题目学习link1
题目学习link2
题目学习link3
%%% 受益匪浅&＃xff01;
&＃xff0d;&＃xff0d;&＃xff0d;&＃xff0d;&＃xff0d;&＃xff0d;&＃xff0d;&＃xff0d;&＃xff0d;&＃xff0d;&＃xff0d;&＃xff0d;&＃xff0d;&＃xff0d;&＃xff0d;&＃xff0d;&＃xff0d;&＃xff0d;&＃xff0d;&＃xff0d;&＃xff0d;&＃xff0d;&＃xff0d;&＃xff0d;&＃xff0d;&＃xff0d;&＃xff0d;&＃xff0d;&＃xff0d;&＃xff0d;&＃xff0d;&＃xff0d;

通过了解题意可知
当 n &＃xff1d; 2 时 为一种特殊情况&＃xff0c;特判一下(样例温和捏~
当 n > 2 时 当一个节点为good节点时&＃xff0c;与其相连的节点一定为非good点
这样模型就显现出来了 类似于link2中所讲树的最小点覆盖问题
这里用 0 表示 该点不是good点 , 1 表示为good点
且只有 0&＃xff0d;0 &＃xff0c; 0&＃xff0d; 1 两种情况&＃xff0c;dp即可求出最大的 good 点个数
由于还要求最小的节点权值和&＃xff0c;开个结构体用dp数组一起求
状态转移见代码

/**&＃64;author:bzdhxs*&＃64;date:2022/03/15*&＃64;URL:
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
template <typename T>
inline void read(T &s){s &＃61; 0;T w &＃61; 1, ch &＃61; getchar();while (!isdigit(ch)) { if (ch &＃61;&＃61; &＃39;-&＃39;) w &＃61; -1; ch &＃61; getchar(); }while (isdigit(ch)) { s &＃61; (s << 1) &＃43; (s << 3) &＃43; (ch ^48); ch &＃61; getchar();} s *&＃61; w;}
template <typename T>
inline void write(T s){if (s < 0) putchar(&＃39;-&＃39;), s &＃61; -s;if (s > 9) write(s / 10);putchar(s % 10 &＃43; &＃39;0&＃39;);}
#define int long long
#define _orz ios::sync_with_stdio(false),cin.tie(0)
#define mem(str,num) memset(str,num,sizeof(str))
#define forr(i,a,b) for(int i &＃61; a; i <&＃61; b;i&＃43;&＃43;)
#define forn(i,n) for(int i &＃61; 0; i
#define dbg() cout <<"0k!"<
typedef long long ll;
int pri[16] &＃61; {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
const int inf &＃61; 0x3f3f3f3f;
const int INF &＃61; ~0ULL;
const int N &＃61; 1e6&＃43;10;int n;
vector<int> g[200005];
struct node{int g,s; // g 记录好点个数 s 记录权值和//用来取较优的点bool operator>(const node&t)const{if(g !&＃61; t.g) return g > t.g; //优先good点个数&＃xff0c;相同取权值小的return s < t.s;}
}dp[200005][2];//树形dp
void dfs1(int u,int fa){dp[u][0].s &＃61; 1;// 非good点权值为1&＃xff0c;最小dp[u][1].s &＃61; g[u].size();// 作为good点权值为直接连边的个数dp[u][1].g &＃61; 1;// 为good点故为1for(auto v:g[u]){if(v &＃61;&＃61; fa) continue;dfs1(v,u);// u作为good点dp[u][1].g &＃43;&＃61; dp[v][0].g; // 直接连边的均为非good点取dp[v][0]dp[u][1].s &＃43;&＃61; dp[v][0].s;// 当 u为非good点的时候&＃xff0c;v可以为good 也可以为非good 取最优&＃xff1b;int best &＃61; (dp[v][0] > dp[v][1])?0:1;dp[u][0].g &＃43;&＃61; dp[v][best].g;dp[u][0].s &＃43;&＃61; dp[v][best].s;}
}int w[200005];// 再次遍历更新点的权值
void dfs2(int u,int fa,int bes){// good 就取相连点个数 否则取1&＃xff1b;w[u] &＃61; (bes)?g[u].size():1;for(auto v:g[u]){if(v &＃61;&＃61; fa) continue;// 当前节点为good那么相邻节点就为非goodif(bes) dfs2(v,u,0);else{int best &＃61; (dp[v][0] > dp[v][1])?0:1;dfs2(v,u,best);}}
}
signed main()
{cin >> n;forr(i,1,n-1){int l,r;cin >> l >> r;g[l].push_back(r);g[r].push_back(l);}//特判2if(n &＃61;&＃61; 2){cout << 2 <<" " << 2 << endl;cout << 1 <<" "<< 1 << endl;return 0;}dfs1(1,0);int best &＃61; (dp[1][0] > dp[1][1])?0:1;//求每个点的权值dfs2(1,0,best);// 输出1节点最优情况cout << dp[1][best].g <<" "<<dp[1][best].s<<endl;forr(i,1,n) cout << w[i] <<" \n"[i&＃61;&＃61;n];return 0;
}