Article From:https://www.cnblogs.com/MikuKnight/p/9063293.html

At the beginning, the limit of 1 is assigned to infinity, and then greedy for each node, from the big to the small, the maximum value of the element can be less than 0.

Pay attention to the uniqueness of the comparison

#include<cstdio>
#include<cctype>
#include<algorithm>
#define maxn 100002
using namespace std;
bool vis[maxn];
int n,f[maxn],cnt,tmp[maxn],head[maxn],to[maxn<<1],nex[maxn<<1],inc[maxn],lim[maxn];
void read(int &x){
    char ch=getchar();x=0;int f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    x*=f;
}
void addedge(int u,int v){to[++cnt]=v;nex[cnt]=head[u];head[u]=cnt;}
bool cmp1(int a,int b){return f[a]>f[b];}
void dfs(int now,int fa){
    f[now]=inc[now];
    for(int i=head[now];i;i=nex[i])if(to[i]!=fa)dfs(to[i],now);
    int hd=0,tail=0;
    for(int i=head[now];i;i=nex[i])if(to[i]!=fa)tmp[++tail]=to[i];
    sort(tmp+1,tmp+tail+1,cmp1);
    while(hd<min(lim[now]-1,tail) && f[tmp[hd+1]]>=0)f[now]+=f[tmp[++hd]],vis[now]|=vis[tmp[hd]];
    if(hd<tail && hd>0 && f[tmp[hd]]==f[tmp[hd+1]] || f[tmp[hd]]==0 && hd>0) vis[now]=1;
}

int main(){
    read(n);
    int x,y;
    for(int i=2;i<=n;i++)read(inc[i]);
    for(int i=2;i<=n;i++)read(lim[i]);lim[1]=1e9;
    for(int i=1;i<n;i++){read(x);read(y);addedge(x,y);addedge(y,x);}
    dfs(1,0);
    printf("%d\n",f[1]);
    if(vis[1])printf("solution is not unique");else printf("solution is unique");
}

 

Link of this Article: bzoj4472

Leave a Reply

Your email address will not be published. Required fields are marked *