[JSOI2015]SALESMAN

输入的第一行是一个正整数ｎ(5 ≤ n ≤ 100000)，表示城镇数目。城镇以１到ｎ的数命名。小T的家乡命名为１。
第二行和第三行都包含以空格隔开的ｎ－１个整数，第二行的第ｉ个数表示在城镇ｉ＋１停留的净收益。
第三行的第ｉ个数表示城镇ｉ＋１规定的最大停留次数。
所有的最大停留次数都不小于２。接下来的ｎ－１行每行两个１到ｎ的正整数ｘ，ｙ，之间以一个空格隔开，表示ｘ，ｙ之间有一条不经过其它城镇的双向道路。
输入数据保证所有城镇是连通的。

输出有两行，第一行包含一个自然数，表示巡回旅行的最大收益。
如果该方案唯一，在第二行输出“solution is unique”，否则在第二行输出“solution is not unique”。

C++11(clang++ 3.9) 解法, 执行用时: 64ms, 内存消耗: 3684K, 提交时间: 2019-03-16 12:45:13

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=100005;

int cnt,n,val[N],lim[N],last[N],a[N],a1,f[N],g[N];
struct edge{int to,next;}e[N*2];

void addedge(int u,int v)
{
    e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
    e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;
}

bool cmp(int a,int b)
{
    return f[a]>f[b];
}

void dfs(int x,int fa)
{
    f[x]=val[x];
    for (int i=last[x];i;i=e[i].next)
        if (e[i].to!=fa) dfs(e[i].to,x);
    a1=0;
    for (int i=last[x];i;i=e[i].next) 
        if (e[i].to!=fa) a[++a1]=e[i].to;
    sort(a+1,a+a1+1,cmp);
    int p=0;
    while (p<min(lim[x]-1,a1)&&f[a[p+1]]>=0) p++,f[x]+=f[a[p]],g[x]|=g[a[p]];
    if (p<a1&&p>0&&f[a[p]]==f[a[p+1]]||f[a[p]]==0&&p>0) g[x]=1;
}


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

详情