『GROI-R1』继续深潜，为了同一个梦想 题解

· · 题解

验题人题解

考虑一个集合中一个点能产生贡献的情况。此时该点被集合包含，集合内的所有点在同一条树链上，且该集合中有至少两个点。

显然，一个点 u 在一条长度为 l 的链上产生的贡献为 2^{l-1}-1（除去 u 每个点选或不选，再去掉只剩 u 一个点的情况）。

由此延伸到一个点 u 的总贡献：假定整棵树以 u 为根，对每棵子树统计出从子树根出发的方案数（不包含全不选）。对于单棵子树，设其方案数为 x，则贡献为 x；对于不同的两棵子树，设其方案数分别为 x,y，则贡献为 xy。只不过此时单个子树的方案数并非简单的 2 的次幂，而是由它下方的子树合并而来。

考虑原题。对于结点 u，在以 u 为根的子树中按上述方法统计一遍，再将子树内与子树外的进行一次合并统计。由于方法多样，且参考代码中有较详细的注释，具体实现方式此处不细讲。

时间复杂度 O(n)，优于 std。

参考代码

非唯一解法，仅供参考。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define _ 1000005
#define Mod 1000000007
void pls(ll &x,ll y){x=(x+y)%Mod;}
ll n,x,y,a[_],ans,s[_],cnt,hd[_];
//a[u]: 在以u为根的子树内，u必选，其余点可以全不选，
//且所有集合内的点都在同一条以u为一端的链上的方案数
struct o{ll nxt,to;}edg[_];
void add(ll x,ll y){edg[++cnt].nxt=hd[x];hd[x]=cnt;edg[cnt].to=y;}
//这里由于代码习惯，所有的u都写成了x，请见谅
void dfs1(ll x,ll fa){
    a[x]=1;
    for(ll i=hd[x];i;i=edg[i].nxt)if(edg[i].to!=fa){
        dfs1(edg[i].to,x);
        pls(s[x],(a[x]-1)*(a[edg[i].to]*2-1));//统计当前子树内部产生的贡献
        pls(a[x],a[edg[i].to]*2-1);//更新当前子树下的方案数
    }
}
void dfs2(ll x,ll fa,ll z){//z: 该子树外的方案数（限制同a[u]）
    pls(s[x],a[x]*z-1);//直接统计穿过子树内外的链产生的贡献
    for(ll y,i=hd[x];i;i=edg[i].nxt)if(edg[i].to!=fa){
        y=edg[i].to;
        dfs2(y,x,((a[x]-a[y]*2+1+Mod*2)%Mod+z-1)*2%Mod);//更新
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(ll i=1;i<n;i++)cin>>x>>y,add(x,y),add(y,x);
    dfs1(1,0);dfs2(1,0,1);
    for(ll i=1;i<=n;i++)ans^=s[i]*i;
    cout<<ans<<'\n';
}