求调D，马蜂良好

水星湖 @ 2024-07-31 00:46:24

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 5;

int n, t, x, a[N];
vector<int> p[N];

void dfs(int u) {
    for(auto v : p[u]) 
        dfs(v);
    if(!p[u].size()) return;
    int x = 2e9;
    for(int v : p[u]) 
        x = min(x, (int)(floor((a[v] - a[u]) / 2.0)));
    if(u != 1) 
        a[u] += x;
    else {
        int minn = 2e9;
        for(int v : p[u])
            minn = min(minn, a[v]);
        a[u] += minn;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> t;
    while(t--) {
        cin >> n;
        for(int i = 1; i <= n; i++) cin >> a[i];
        for(int i = 1; i <= n; i++) p[i].clear();
        for(int i = 2; i <= n; i++) {
            int u; cin >> u;
            p[u].push_back(i);
        }
        dfs(1);
        cout << a[1] << endl;
    }
    A

    return 0;
}

by System_Error_ @ 2024-07-31 00:50:02

这么卷（

by Mr_Az @ 2024-07-31 00:51:55

我跟你一样，开ull要不然会炸，要不然就特判。

我红温了，我要炸了。

by System_Error_ @ 2024-07-31 00:54:44

@Mr_Az 开ull也不对吧

by steveyang137 @ 2024-07-31 00:55:20

by Mr_Az @ 2024-07-31 00:55:59

@jjh20100730 据说是要的，因为边界情况会炸。

by System_Error_ @ 2024-07-31 00:56:36

@Mr_Az 我int都没炸

by System_Error_ @ 2024-07-31 00:58:52

@水星湖 贴一份我的代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int t,n,a[N],head[N],cnt;
struct node {int to,nxt;}e[N];
void add(int u,int v) {e[++cnt]=(node){v,head[u]};head[u]=cnt;}
int dfs(int u) {
    int mn=INT_MAX;
    for(int i=head[u]; ~i; i=e[i].nxt) {
        int v=e[i].to;
        mn=min(mn,dfs(v));
    }
    if(mn==INT_MAX) return a[u];
    if(u==1) return mn+a[u];
    else {
        if(mn>=a[u]) return (a[u]+mn)/2;
        else return mn;
    }
}
int main() {
    cin>>t;
    while(t--) {
        cin>>n;
        for(int i=1; i<=n; i++) cin>>a[i];
        memset(head,-1,sizeof(head)),cnt=0;
        for(int i=2; i<=n; i++) {
            int p;
            cin>>p;
            add(p,i);
        }
        cout<<dfs(1)<<endl;
    }
    return 0;
}

by System_Error_ @ 2024-07-31 00:59:21

@steveyang137 正确的

by 水星湖 @ 2024-07-31 01:06:51

我纯唐了，我竟然还给根减，给儿子加 草我真傻逼 @jjh20100730 @steveyang137

by System_Error_ @ 2024-07-31 01:07:29

A了吗