ARC169A 题解

Guizy · 2023-12-13 20:23:44 · 题解

思路

不难想到，因为次数有 10^{100}，深度越深，对答案的影响越大。因为深度深的会改变深度浅的，深度浅的又会改变深度更浅的，所以我们只需要统计出每个深度的点的权值和，在按深度从深到浅，看看答案的正负，如果是正的，就输出 +，负的就输出 -，否则继续枚举。如果枚举还不能得到答案，就证明所有的点都是 0，输出 0。

实现

#include<bits/stdc++.h>
#define Max 250010
#define inf 1000000000
using namespace std;

long long n,a[Max],p[Max];
long long sum[Max],dis[Max];
int flag;

signed main(){

    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        dis[i]=inf;//初始化
    }
    dis[1]=0;
    for(int i=2;i<=n;i++){
        scanf("%lld",&p[i]);
        dis[p[i]]=i+1;//预处理深度
    }

    for(int i=1;i<=n;i++)
        if(dis[i]<inf)
            sum[dis[i]]+=a[i];

    for(int i=n;~i;i--){
        if(sum[i]>0) return printf("+"),0;
        if(sum[i]<0) return printf("-"),0;
    }
    printf("0");

    return 0;
}