题目链接：点这里
题解：
需要证明，所求的路径一定是全部权值都为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_pair typedef 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 ",mi); } else { if(2*ans1 > ans2) printf("1/%d ",ans1); else if(ans2 % 2 == 0) printf("1/%d ",ans2/2); else printf("2/%d ",ans2); } return 0; }