多种方案的判断就是看本身选中的子树中和没选的子树中是否存在两个值相等的，这样它们就可以通过互换来到达另一种方案，值得注意的是如果选了一个值为 \(0\) 的子树就必定可以多一种方案出来，，因为这颗子树选或不选都是满足最优的。

这里有个小问题：交到BZOJ上面去它会提示你 sort 没有声明，此时需要 #include <cstdlib> ，具体我也不知道为什么。。。

#include <algorithm> #include <cstdlib> #include <cstdio> #include <vector> #define rg register #define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout) using namespace std; template < class T > inline void read(T& s) { s = 0; int f = 0; char c = getchar(); while ('0' > c || c > '9') f |= c == '-', c = getchar(); while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar(); s = f ? -s : s; } typedef long long LL; const int _ = 1e5 + 5; int tot, head[_]; struct Edge { int v, nxt; } edge[_ << 1]; inline void Add_edge(int u, int v) { edge[++tot] = (Edge) { v, head[u] }, head[u] = tot; } int n, t[_], g[_]; LL a[_], dp[_]; inline bool cmp(int x, int y) { return dp[x] > dp[y]; } inline void dfs(int u, int f) { vector < int > tmp; tmp.clear(); dp[u] = a[u]; for (rg int i = head[u]; i; i = edge[i].nxt) if (edge[i].v != f) dfs(edge[i].v, u), tmp.push_back(edge[i].v); int p = 0, lim = min((int) tmp.size(), t[u] - 1); sort(tmp.begin(), tmp.end(), cmp); while (p < lim && dp[tmp[p]] >= 0) dp[u] += dp[tmp[p]], g[u] |= g[tmp[p]], ++p; if ((p > 0 && p < lim && dp[tmp[p]] == dp[tmp[p - 1]]) || (p > 0 && dp[tmp[p - 1]] == 0)) g[u] = 1; } int main() { #ifndef ONLINE_JUDGE file("cpp"); #endif read(n); for (rg int i = 2; i <= n; ++i) read(a[i]); a[1] = 0; for (rg int i = 2; i <= n; ++i) read(t[i]); t[1] = 2147483647; for (rg int u, v, i = 1; i < n; ++i) read(u), read(v), Add_edge(u, v), Add_edge(v, u); dfs(1, 0); printf("%lld\n", dp[1]); puts(g[1] ? "solution is not unique" : "solution is unique"); return 0; }

「JSOI2015」salesman