(POI) XXI OI Round III (finals) - day 0 (trial) Task FarmCraft

https://szkopul.edu.pl/problemset/problem/dGllMe_Kjqa5SGT9wMo6UGlp/site/?key=statement

很具有想法性的一題XDD

#include <iostream>
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#include <queue>
using namespace std;

const int N = 500006;

vector<int> G[N];
int par[N];
int sz[N];
int deg[N];
int c[N];
vector< pair<int,int> > v[N];

void dfs(int u,int p)
{
    sz[u] = 1;
    if (u!=p)
    {
        deg[p]++;
        //cout<<"p = "<<p<<" , deg = "<<deg[p]<<endl;
    }
    par[u] = p;
    for (int v:G[u])
    {
        if (v != p)
        {
            dfs(v,u);
            sz[u] += sz[v];
        }
    }
}

int solve(vector< pair<int,int> > v)
{
    sort( v.begin(),v.end(),[](const pair<int,int> &p1,const pair<int,int> &p2)
    {
        return p1.first-p1.second > p2.first-p2.second;
    });
    int mx = 0, pre = 0;
    for (pair<int,int> p:v)
    {
        mx = max(mx,p.first + pre);
        pre += p.second;
    }
    return mx;
}

int main ()
{
    int n;
    scanf("%d",&n);
    for (int i=1;n>=i;i++)
    {
        scanf("%d",&c[i]);
    }
    for (int i=1;n>i;i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(1,1);
    queue<int> que;
    for (int i=1;n>=i;i++)
    {
        if (deg[i] == 0)
        {
            que.push(i);
        }
    }
    while (!que.empty())
    {
        int t=que.front();
        que.pop();
        if (t == 1) break;
        //cout<<"t = "<<t<<endl;
        int mx = max(solve(v[t]),c[t]);
        //cout<<"mx = "<<mx<<endl;
        v[par[t]].push_back(make_pair(mx+1,(sz[t])*2));
        deg[par[t]]--;
        if (deg[par[t]] == 0) que.push(par[t]);
    }
    int ans= c[1] + ((n-1)*2);
    ans = max(ans, solve(v[1]));
    printf("%d\n",ans);
}