这个题目比较简单，思路一下就出来了。
维护两个d p ， d p 1 和 d p 2 : dp，dp1和dp2:dp，dp1和dp2:
d p 1 [ i ] : 以 点 i 为 起 点 以 及 子 树 符 合 取 模 递 增 的 最 大 长 度 dp1[i]:以点i为起点以及子树符合取模递增的最大长度dp1[i]:以点i为起点以及子树符合取模递增的最大长度
d p 2 [ i ] : 以 点 i 为 起 点 以 及 子 树 符 合 取 模 递 减 的 最 大 长 度 dp2[i]:以点i为起点以及子树符合取模递减的最大长度dp2[i]:以点i为起点以及子树符合取模递减的最大长度
答案就是：a n s = m a x ( a n s , Σ ( d p 1 [ i ] + d p 2 [ i ] − 1 ) ) ans=max(ans,\Sigma (dp1[i]+dp2[i]-1))ans=max(ans,Σ(dp1[i]+dp2[i]−1))
代码：
/********************************************************************* 程序名: 版权: 作者: Joecai 日期: 2022-05-21 13:19 说明: *********************************************************************/ #include <bits/stdc++.h> using namespace std; #define x first #define y second # define rep(i,be,en) for(int i=be;i<=en;i++) # define pre(i,be,en) for(int i=be;i>=en;i--) #define ll long long #define endl "\n" #define LOCAL #define pb push_back #define int long long typedef pair<ll, ll> PII; #define eb emplace_back #define sp(i) setprecision(i) const int N = 5e5 + 10, INF = 0x3f3f3f3f; int n; vector<int>g[N]; int w[N]; int dp1[N];//以这个点开始的如0 1 2 0 int dp2[N]; int ans = 0; void dfs(int u, int fa) { dp1[u] = 1; dp2[u] = 1; for (auto x : g[u]) { if (x == fa) continue; dfs(x, u); if ((w[x]) % 3 == (w[u] + 1) % 3) { dp1[u] = max(dp1[u], dp1[x] + 1); } if (w[x] % 3 == (w[u] - 1 + 3) % 3) { dp2[u] = max(dp2[u], dp2[x] + 1); } } ans = max(dp1[u] + dp2[u] - 1, ans); } void solve() { cin >> n; for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); } for (int i = 1; i <= n; i++) { cin >> w[i]; } dfs(1, -1); cout << ans << endl; } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); //#ifdef LOCAL //freopen("data.in.txt","r",stdin); //freopen("data.out.txt","w",stdout); //#endif int __ = 1; //cin>>__; while (__--) { solve(); } return 0; }
