网站免费推广方案,长沙房地产网站设计,wordpress扫描器,手工活外包加工官方网Problem - H - Codeforces 题意#xff1a; 思路#xff1a;
这题应该算是铜牌题
铜牌题 简单算法 基础思维
简单复盘一下思路
首先#xff0c;我们发现有个很特殊的条件#xff1a; ti 3
然后看一下样例#xff1a; 注意到#xff0c;对于一个结点 u #…Problem - H - Codeforces 题意 思路
这题应该算是铜牌题
铜牌题 简单算法 基础思维
简单复盘一下思路
首先我们发现有个很特殊的条件 ti 3
然后看一下样例 注意到对于一个结点 u 如果它的所有子节点中没有 tv 3的那么就肯定是沿着一棵子树走到底然后去走剩下的子树
如果所有子节点中有 tv 3的那么可以先走到某个子节点然后再走到这个 tv 3的结点
注意到了子问题那么很自然地去考虑树DP
注意到子问题可以分类成不算结点u 和 算结点u 因此可以这样设计状态
设 dp[u] 为没有走过结点 u的这棵子树的贡献
然后考虑转移
因为 ti 3 考虑在转移的时候暴力分讨
因为怎么转移和这些子节点中是否存在 tv 3的结点有关那么考虑先去把这些结点遍历一遍看看是否存在然后去转移
如果存在那么就是先走到某个结点再走到这个tv 3的结点
考虑枚举这个“某个结点”注意到tv 3的结点可能会有多个我们贪心地保留av最大的那个这个可以考虑用multiset维护
为了计算贡献我们设sum[u]表示所有子节点的 dp[v] 之和
此时的贡献为
dp[u] max{sum[u] - dp[v] sum[v] a[v] *rbegin()}
然后考虑不存在tv 3的结点那么就是一次性走到底再去遍历其他结点此时贡献为 sum[u] mx其中 mx 为所有子节点中最大的 a[v]
为了防止出问题我们在原来的multiset中先插入 -Inf
Code
#include bits/stdc.h#define int long longusing i64 long long;constexpr int N 1e5 10;
constexpr int M 1e5 10;
constexpr int P 2e2 10;
constexpr i64 Inf 1e18;
constexpr int mod 1e9 7;
constexpr double eps 1e-6;std::vectorint adj[N];int n;
int a[N], t[N];
int dp[N], sum[N];void dfs(int u, int fa) {std::multisetint S;int mx 0;for (auto v : adj[u]) {if (v fa) continue;dfs(v, u);sum[u] dp[v];mx std::max(mx, a[v]);if (t[v] 3) S.insert(a[v]);}dp[u] sum[u] mx;S.insert(-0x3f3f3f3f);for (auto v : adj[u]) {if (v fa) continue;if (t[v] 3) S.erase(S.find(a[v]));dp[u] std::max(dp[u], sum[u] - dp[v] sum[v] a[v] (*S.rbegin()));if (t[v] 3) S.insert(a[v]);}
}
void solve() {std::cin n;for (int i 1; i n; i ) {sum[i] dp[i] 0;adj[i].clear();}for (int i 1; i n; i ) {std::cin a[i];}for (int i 1; i n; i ) {std::cin t[i];}for (int i 1; i n - 1; i ) {int u, v;std::cin u v;adj[u].push_back(v);adj[v].push_back(u);}dfs(1, -1);std::cout dp[1] a[1] \n;
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t 1;std::cin t;while (t--) {solve();}return 0;
}
