题解 P6082 【[JSOI2015]salesman】

容易注意到原图是棵树。 我们设 $w_u$ 表示 在 $u$ 停留的净收益， $d_u$ 表示能够在 $u$ 停留的最大次数， $dp_u$ 表示经过 $u$ 及其子树的最大收益，则 $dp_u=w_u+u$ 的几个儿子中收益最大的且收益非负的前 $d_u-1$ 个的收益之和 我们计算完 $u$ 的所有儿子的答案后将儿子按照收益从大到小排序取前面不超过 $d_u-1$ 个非负的即可。 这样完成了第一问。 第二问的多解情况只有两种可能: 1. 存在一种最优方案使得经过的某个点 $u$ 满足 $dp_u=0$ 。 2. 存在一种最优方案使得经过的某个点 $u$ 存在至少 $d_u$ 个儿子， 且第 $d_u$ 大收益非负的儿子不唯一。 我们只需要在 $dp$ 的过程中顺便记录是否存在这两种情况即可。 瓶颈在给儿子排序， 总时间复杂度 $O(n\log n)$ 。 代码: ```cpp #include<bits/stdc++.h> #define Rep(i,a,b) for(register int i=(a);i<=(b);++i) #define Repe(i,a,b) for(register int i=(a);i>=(b);--i) #define rep(i,a,b) for(register int i=(a);i<(b);++i) #define pb push_back typedef long long ll; using namespace std; const int MAXN = 1e5 + 7; static int w[MAXN], d[MAXN], n; vector <int> ed[MAXN]; inline void init() { cin >> n; Rep(i, 2, n) cin >> w[i]; Rep(i, 2, n) cin >> d[i], -- d[i]; d[1] = n; static int u, v; Rep(i, 1, n - 1) cin >>u >> v, ed[u].pb(v), ed[v].pb(u); } static ll dp[MAXN]; static int nu[MAXN]; static int sn[MAXN]; inline bool cmp(int u, int v) {return dp[u] > dp[v];} void dfs(int u, int fa) { for(int v : ed[u]) if(v ^ fa) dfs(v, u); int e = 0; dp[u] = w[u]; for(int v : ed[u]) if(v ^ fa) sn[++ e] = v; if(!e) return; sort(sn + 1, sn + e + 1, cmp); Rep(i, 1, min(e, d[u])) { if(i[sn][dp] > 0) dp[u] += i[sn][dp], nu[u] |= i[sn][nu]; if(i[sn][dp] == 0) nu[u] = 1; } if(d[u] < e && u[d][sn][dp] > 0 && (d[u] + 1)[sn][dp] == u[d][sn][dp]) nu[u] = 1; } inline void solve() { dfs(1, 0); cout << dp[1] << endl; if(nu[1]) cout << "solution is not unique" << endl; else cout << "solution is unique" << endl; } int main() { init(); solve(); return 0; } ```