Luogu

分析

首先,一个点能停留 $s$ 次,等价于可以进入它的 $s-1$ 棵子树。

先考虑第一问。 $dp_{i}$ 表示以 $i$ 为根的子树的最大收益,转移时在所有 $dp$ 值非负的子树选最大的那些进入即可。

再考虑第二问。设 $f_i$ 表示以 $i$ 为根的子树中最大收益是否唯一。如果当前子树最大收益不唯一,那么有以下可能:

  • 一棵子树最大收益不唯一。
  • 选了一棵最大收益为 $0$ 的子树。
  • 存在一棵未选的子树,满足它和某棵选了的子树的最大收益相同。

那么就很好转移了。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;
 
inline int read() {
    int 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;
}

const int N=100000+10;

int n,w[N],c[N];

struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
    static int c=0;
    e[++c]=(edge){v,head[u]},head[u]=c;
}

int dp[N],f[N];
vector<int> vec;

inline int cmp(int x,int y) { return dp[x]>dp[y]; }
inline void dfs(int u,int fa) {
    dp[u]=w[u];
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=fa) dfs(e[i].v,u);
    vec.clear();
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=fa&&dp[e[i].v]>=0) vec.push_back(e[i].v);
    sort(vec.begin(),vec.end(),cmp);
    int lim=min((int)vec.size(),c[u]-1);
    for (re int i=0;i<lim;++i) dp[u]+=dp[vec[i]],f[u]|=f[vec[i]];
    if (lim&&!dp[vec[lim-1]]) f[u]=1;
    if (lim<vec.size()&&dp[vec[lim-1]]==dp[vec[lim]]) f[u]=1;
}

int main() {
    n=read();
    for (re int i=2;i<=n;++i) w[i]=read();
    for (re int i=2;i<=n;++i) c[i]=read(); c[1]=N;
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    dfs(1,0); printf("%d\n",dp[1]);
    puts(f[1]?"solution is not unique":"solution is unique");
    return 0;
}
最后修改:2020 年 02 月 27 日 09 : 20 AM