题意
给定一棵\(n\)个点的树，有点权，你从\(1\)号点开始一次旅行，最后回到\(1\)号点。每到达一个点，你就能获得等于该点点权的收益， 但每个点都有进入该点的次数限制，且每个点的收益只能获得一 次，求最大收益。
思路
树形\(\texttt{DP}\) + 优先队列
比较容易看出来这是一道树形\(\texttt{DP}\)题
要注意的是最大停留次数为输入次数-1，因为还要从子树返回到这一个节点
然后下面考虑怎么\(\texttt{DP}\)
我们用\(f[i]\)表示以从\(i\)出发，访问以\(i\)为根的子树，并且最后能回到\(i\)的最大收益
显然我们要选较大且非负的数，因为去大点权的节点肯定比去小点权的点权更优，去非负点权的节点肯定比去负点权的节点更优，而且因为一个节点可以去多次且只记一次点权，所以肯定能够用完次数，因此我们每次在小于等于停留次数的前提下取完正儿子即可，这样就可以保证最大，所以\(f[i]\)就等于\(i\)所有正儿子的点权之和（前提是小于等于最大停留次数），最后的答案就是\(f[1]\)
下面来考虑解是否唯一的问题，解不唯一有两种情况：
- \(i\)的子树中有权值为\(0\)的点。因为选不选权值都不变，所以可选可不选，因此解就不唯一了
- 如果\(i\)在遍历过程中当父亲节点剩余的停留次数为\(1\)时，可选的最大值有两个及两个以上儿子节点，则解不唯一
所以在过程中判断一下就好了
代码
/*
Author:loceaner
*/
#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int A = 5e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar(); int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == ‘-‘) f = -1;
for( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
int n, cnt, head[A], ti[A], a[A], f[A], flag[A];
struct node { int to, nxt; } e[A];
inline void add(int from, int to) {
e[++cnt].to = to;
e[cnt].nxt = head[from];
head[from] = cnt;
}
struct Node {
int val, id;
Node() { val = id = 0; }
Node(int a, int b) { val = a; id = b; }
bool operator < (const Node &A) const {
return val < A.val;
}
};
void dfs(int x, int fa) {
priority_queue <Node> q;
f[x] = a[x];
for (int i = head[x]; i; i = e[i].nxt) {
int to = e[i].to;
if (to == fa) continue;
dfs(to, x);
q.push(Node(f[to], flag[to]));
}
int vis = 0, last;
while (++vis <= ti[x] && !q.empty()) {
Node tmp = q.top(); q.pop();
if (tmp.val < 0) break;
if (tmp.val == 0) { flag[x] = 1; break; }
f[x] += tmp.val;
flag[x] |= tmp.id;
last = tmp.val;
}
if (!q.empty())
if (q.top().val == last) flag[x] = 1;
}
int main() {
n = read();
ti[1] = inf; //根节点可以访问无限次
for (int i = 2; i <= n; i++) a[i] = read();
for (int i = 2; i <= n; i++) ti[i] = read() - 1;
//最多遍历ti[i]-1次因为还要从子树回到这个节点
for (int i = 1, x, y; i < n; i++) {
x = read(), y = read();
add(x, y), add(y, x);
}
dfs(1, 0);
cout << f[1] << ‘\n‘;
if (flag[1]) cout << "solution is not unique\n";
else cout << "solution is unique\n";
return 0;
}