Tree Constructe(icpc济南）(二分图+构造）

题意：
题目提供一棵树，需要你给树上每个结点构造一个值 \(a[i]\) \((0<=a[i]<2^{60})\)，其中要保证，两个有连边的结点的或和为 \(2^{60}-1\)，即 \(a[x]\ or\ a[y] = 2^{60}-1\) \((x和y有边)\)。

想法：

• 首先考虑其中是分为有边和无边两种情况，就可以想到二分图，树本身就是一幅二分图，接下来通过dfs对每个结点染色。

• 对于染色后的点，我们分为白点和黑点，设白点的数量比较少。首先对于黑点和白点需要满足点条件是黑点之间和白点之间都不存在边，即两者都或值不等于 \(2^{60}-1\ ((1<<60)-1)\)。考虑白点，给白点编号，设白点初始值为 \(2^{60}-1\) ，然后让每个白点的最高位都为 \(0\)，就可以保证白点间不存在边。然后让每个白点从低向高的第 \(id\) 位变成 \(0\)。

• 考虑黑点，因为每个白点只有两位为 \(0\)，所以黑点初始最高位为 \(1\)，即初始值为 \(2^{59}\)，接下来考虑怎么让黑点连边，那么只需要把和黑点相连点的白点的自低向高的 \(id\) 位变成 \(1\)即可。最终每两个黑点之间通过 \(or\) 操作最多只有 \(8\) 个 \(1\)，即不可能有连边，而黑点和相连白点间通过 \(or\) 可以把黑点为 \(0\) 处补为 \(1\) ，正好相连。

代码：

vector<int>g[105];
int n;
vector<int>color[5];
int id[105];
ll ans[105];
void dfs(int now,int fa,int col)
{
    color[col].push_back(now);
    for(int i=0;i<g[now].size();i++){
        int v=g[now][i];
        if(v==fa)continue;
        dfs(v,now,col^1);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,-1,0);
    if(color[0].size()>color[1].size()){
        swap(color[0],color[1]);
    }
    for(int i=0;i<color[0].size();i++){
        int nn=color[0][i];
        id[nn]=i;
        ans[nn]=(1ll<<60)-1-(1ll<<i)-(1ll<<59);
    }
    for(int i=0;i<color[1].size();i++){
        int nn=color[1][i];
        ans[nn]=(1ll<<59);
        for(int j=0;j<g[nn].size();j++){
            int num=id[g[nn][j]];
            ans[nn]+=(1ll<<num);
        }
    }
    for(int i=1;i<=n;i++){
        printf("%lld%c",ans[i]," \n"[i==n]);
    }
}

Tree Constructe(icpc济南）(二分图+构造）

原文：https://www.cnblogs.com/ha-chuochuo/p/14315637.html