题面

题解

考虑树形 DP , 设 \(f[i]\) 为 \(i\) 节点为根的子树最大收益是多少, \(h[i]\) 代表 \(i\) 节点的最优方案是否唯一

转移的话拿个堆记一下子节点中 \(>0\) 的那些, 然后 \(h\) 跟他们的与一下

若是剩下来的有 \(f = 0\) 或是跟你选的是一样的, 这个点 \(i\) 的 \(h\) 就计为 \(0\)

Code

#include <algorithm>#include <iostream>#include <cstring>#include <cstdio>#include <queue>#define mp(i, j) make_pair(i, j)const int N = 1e5 +5;const int INF = 0x3f3f3f3f; using namespace std;int n, f[N], tm[N], h[N], head[N], cnte;struct edge { int to, nxt; } e[N << 1]; priority_queue<pair<int, int> > q; template < typename T >inline T read(){ T x = 0, w = 1; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); } while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * w; }inline void adde(int u, int v) { e[++cnte] = (edge) { v, head[u] }, head[u] = cnte; }void dfs(int u, int fa){ for(int v, i = head[u]; i; i = e[i].nxt) { v = e[i].to; if(v == fa) continue; dfs(v, u); } while(!q.empty()) q.pop(); int tmp = INF; for(int v, i = head[u]; i; i = e[i].nxt) if((v = e[i].to) != fa) q.push(mp(f[v], v)); while(!q.empty() && tm[u] && q.top().first > 0) { f[u] += (tmp = q.top().first), h[u] &= h[q.top().second]; q.pop(), tm[u]--; } if(!q.empty() && (q.top().first == tmp || !q.top().first)) h[u] = 0; }int main(){ n = read <int> (); for(int i = 2; i <= n; i++) f[i] = read <int> (); for(int i = 2; i <= n; i++) tm[i] = read <int> () - 1; tm[1] = INF, memset(h, 1, sizeof(h)); for(int u, v, i = 1; i < n; i++) u = read <int> (), v = read <int> (), adde(u, v), adde(v, u); dfs(1, 0); printf("%d\n", f[1]); puts(h[1] ? "solution is unique" : "solution is not unique"); return 0; }