Link

ARC169 A Please Sign

Question

给出 长度为 \(n\) 的数组 \(A\)，以及长度为 \(n-1\) 的数组 \(P\)，满足 \(P_i<i\)，\(P\) 标号为 \(2\sim n\)

每一轮操作为 \(A_{P_i} \leftarrow A_i+A_{P_i}\)

求 无限轮后，\(A_1\) 值的正负性

Solution

由于 \(P_i<i\) 所以可以把问题抽象成树，\(A_i\) 表示结点，\(P_i-i\) 表示边，其中 \(P_i\) 为 \(i\) 的父节点，每次操作相当于把父节点的值减去子节点的值

我们发现，深度最深的点起决定性作用，因为无限次之后

如果深度最深的点是负的，那么肯定能把深度较浅的点减成负的。如果深度最深的点是正的，那么肯定能把深度较浅的点加成正的。

往往深度最深的不是一个点，如果深度最深的那些点的加和为 \(0\)，那么就看深度第二深的点集的加和以此类推，直到非零为止

如果加和都为 \(0\)，那么就有 \(A_1\) 的初始状态来决定答案

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=24;
typedef long long LL;
LL a[maxn],ans;
vector<int> G[maxn];
LL vis[maxn];
int p[maxn];
int dep[maxn];
void DFS(int x,int dp){
    dep[x]=dp;
    for(auto v:G[x]){
        DFS(v,dp+1);
    }
}
int main(){
    int N;
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
        scanf("%lld",&a[i]);
    for(int i=2;i<=N;i++){
        scanf("%d",&p[i]);
        G[p[i]].push_back(i);
    }
    DFS(1,0);
    for(int i=2;i<=N;i++)
        vis[dep[i]]+=a[i];
    for(int i=N;i>=1;i--){
        if(vis[i]!=0){
            if(vis[i]>0)
                {printf("+\n");return 0;}
            else 
                {printf("-\n");return 0;}
        }
    }
    if(a[1]>0)
        {printf("+\n");return 0;}
    else if(a[1]<0)
        {printf("-\n");return 0;}
    else 
        {printf("0\n");return 0;}
    return 0;
}