2023icpc省赛 1/12

C题

正常写的话就组合数搞一搞

但是不取模，那么问题就有趣起来了

众所周知，Σc(奇数,sum)=Σ(偶数,sum)，是很对称的

对于x的贡献，如果选x，就可以在儿子里任选奇数个或者偶数个，可以发现对答案的贡献是只选自己时的情况，+a[x]

如果不选x，就必须选至少两个子树里的。大部分情况都是对称的。不对称的情况是只选每个儿子的子树里的，选0个的情况。所以对于每个儿子都-a[x]

找找规律：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read()
{
    ll x;scanf("%lld",&x);return x;
}
int fa[100],d[100],sum[100];
int n;
vector<int>e[100],a;
int lca(int x,int y)
{
    while(d[x]>d[y])
        x=fa[x];
    while(d[x]<d[y])
        y=fa[y];
    while(x!=y)
        x=fa[x],y=fa[y];
    return x;
}
void dfs(int x)
{
    for(auto y:e[x])
    {
        if(y==fa[x])continue;
        fa[y]=x;
        d[y]=d[x]+1;
        dfs(y);
    }
}
void work(int d)
{
    if(d==n+1)
    {
        if(a.size()==0)return ;
        int t=a[0];
        for(auto x:a)
            t=lca(x,t);
        if(a.size()&1)
            sum[t]++;
        else
            sum[t]--;
        return ;
    }
    a.push_back(d);
    work(d+1);
    a.pop_back();
    work(d+1); 
}
int main()
{
    n=read();
    for(int i=1;i<n;i++)
    {
        int x=read(),y=read();
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1);
    work(1);
    for(int i=1;i<=n;i++)
        cout<<sum[i]<<' ';
}

可以ac的代码(大概：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read()
{
    ll x;scanf("%lld",&x);return x;
}
int n;
ll sum[200010],ans;
int main()
{
    n=read();
    for(int i=1;i<n;i++)
        sum[read()]--;
    for(int i=1;i<=n;i++)
        ans+=(1-sum[i])*read();
    cout<<ans;
}