Codeforces Round #660 (Div. 2)

AB

签到

C

计算子树内的人总数，然后可以计算出经过此节点时开心的人数目，然后若存在节点开心人数目小于儿子之和，则输出NO，反之输出YES，注意特判特殊情况

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+7;
int T,n,a[N],h[N];
bool yes;
vector<int>G[N];
void dfs(int u,int f)
{
    for(int i=0;i<G[u].size();i++)
    if(G[u][i]!=f)dfs(G[u][i],u),a[u]+=a[G[u][i]];
}
void dfs2(int u,int f)
{
    int sum=0;
    for(int i=0;i<G[u].size();i++)
    if(G[u][i]!=f)dfs2(G[u][i],u),sum+=h[G[u][i]];
    if(sum>h[u])yes=0;
}
signed main()
{
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld%*d",&n);
        for(int i=1;i<=n;i++)G[i].clear();
        for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
        for(int i=1;i<=n;i++)scanf("%lld",&h[i]);
        for(int i=1,x,y;i<n;i++)scanf("%lld%lld",&x,&y),G[x].push_back(y),G[y].push_back(x);
        dfs(1,0);
        yes=1;
        for(int i=1;i<=n;i++)
        if((h[i]%2+2)%2!=a[i]%2||h[i]>a[i]||h[i]<-a[i]){yes=0;break;}
        else h[i]=a[i]-(a[i]-h[i])/2;
        if(!yes){puts("NO");continue;}
        dfs2(1,0);
        if(yes)puts("YES");else puts("NO");
    }
}

D

反向连边，然后构成一个森林，扫一遍即可，判断若儿子总和大于0则先加，反之最后一块加，注意后加从上往下扫

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
typedef long long ll;
int n,cnt,p[N],vis[N],isrt[N];
ll ans,a[N];
vector<int>G[N];
void dfs(int u)
{
    if(!G[u].size())return;
    for(int i=0;i<G[u].size();i++)dfs(G[u][i]);
    for(int i=0;i<G[u].size();i++)
    if(a[G[u][i]]>0)vis[G[u][i]]=1,p[++cnt]=G[u][i],a[u]+=a[G[u][i]],ans+=a[G[u][i]];
}
void check(int u)
{
    if(!vis[u])p[++cnt]=u,ans+=a[u];
    for(int i=0;i<G[u].size();i++)check(G[u][i]);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=1,x;i<=n;i++)
    {
        scanf("%d",&x);
        if(x!=-1)G[x].push_back(i);
        else isrt[i]=1;
    }
    for(int i=1;i<=n;i++)if(isrt[i])dfs(i);
    for(int i=1;i<=n;i++)if(isrt[i])check(i);
    printf("%lld
",ans);
    for(int i=1;i<=n;i++)printf("%d ",p[i]);
}

用退役前开的号KD-Tree打的。真实手速场。

rank4 rating+=329 nowrating=2083（艹差一点就上橙了，早知道用新号直接上橙了）