首页 > 代码库 > LiberOJ #6210. 「美团 CodeM 决赛」tree 树形DP
LiberOJ #6210. 「美团 CodeM 决赛」tree 树形DP
题目链接：点这里
题解：
需要证明，所求的路径一定是全部权值都为1或者，路径上权值至多有一个为2其余为1且权值2在路径中央。
然后树形DP
设定dp[i][0/1] 以1为根的情况下，以i 节点下子树走分别全1和 走一次2和剩余全走1 的最长链
每遍历一次子树，统计一次答案
下面给出代码
#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define ls i<<1#define rs ls | 1#define mid ((ll+rr)>>1)#define pii pair<int,int>#define MP make_pairtypedef long long LL;const long long INF = 1e18+1LL;const double pi = acos(-1.0);const int N = 5e5+10, M = 1e3+20,inf = 2e9;const LL mod = 1e9+7LL;int n,a[N],ans;int ans1,ans2;vector<int > G[N];int dp[N][2];void dfs(int u,int f) { if(a[u] == 1) dp[u][0] = 1; else if(a[u] == 2) dp[u][1] = 1; for(int i = 0; i < G[u].size(); ++i) { int to = G[u][i]; if(to == f) continue; dfs(to,u); ans1 = max(ans1,dp[to][0] + dp[u][0]); ans2 = max(ans2,dp[u][0] + dp[to][1]); ans2 = max(ans2,dp[u][1] + dp[to][0]); if(a[u] > 2) continue; if(a[u] == 1) { dp[u][0] = max(dp[u][0],dp[to][0] + 1); dp[u][1] = max(dp[u][1],dp[to][1] + 1); } else { dp[u][1] = max(dp[u][1],dp[to][0] + 1); } }}int main(){ scanf("%d",&n); for(int i = 1; i < n; ++i) { int x,y; scanf("%d%d",&x,&y); G[x].push_back(y); G[y].push_back(x); } int mi = inf; for(int i = 1; i <= n; ++i) { scanf("%d",&a[i]); mi = min(mi,a[i]); } ans = 0; dfs(1,0); if(mi >= 2) { printf("%d/1\n",mi); } else { if(2*ans1 > ans2) printf("1/%d\n",ans1); else if(ans2 % 2 == 0) printf("1/%d\n",ans2/2); else printf("2/%d\n",ans2); } return 0;}
LiberOJ #6210. 「美团 CodeM 决赛」tree 树形DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。