題目：

題意：

如果點x和y有連邊，當且僅當a[x] or a[y] = 2⁶⁰ - 1 （兩者是充分必要）
現在給你邊的關系，問你每個點的值應該是多少？（給出一種情況即可）

題解：

構造題，思路非常巧妙
2⁶⁰就是（1<<60）,減去1也就是從第一位到第59位都是1（第六十位是0省略了）
首先01染色，將點分為黑點和白點，讓白色的點為個數少一些的
選數量較少的一組是確保數量小于等于 50
現在每個點都要節點編號id和顏色
id為該點的編號
對于白色的點，我們讓其最高位為0，讓其第id位也是0，其余位置都是1
對于黑色，我們讓其最高位是1，與它相鄰的所有點（也就是白點）的第id位置為1，其余為0

我們來分析分析為什么這樣構造是對的
因為所有白色的最高位是0，所以確保了所有白色之間沒有邊。
白色的點第id為也是0，而與它相鄰的黑點第id位是1，兩者首位也是0和1，正好or后就是2⁶⁰ - 1，這就是確保了黑色與所喲相鄰的白色節點滿足條件
因為黑點除了首位，只要相鄰的白點的第id位是1，所有當一個白點與該黑點不相連時，黑點給不了白點所需要位置上的1

綜上所述就是：黑點所多的（也就是1的部分）是相鄰白點所缺的位置
這個構圖不禁讓人感嘆，妙啊~~

代碼：

#include<bits/stdc++.h> typedef long long ll; using namespace std; inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=400; ll ans[maxn],id[maxn]; vector<int>g[maxn],color[2]; void dfs(int x,int fa,int col) {color[col].push_back(x);for(auto v:g[x]){if(v==fa)continue;dfs(v,x,col^1);} } int main() {//cout<<((12312312-2)|1);int n;cin>>n;for(int i=1;i<n;i++){int u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}dfs(1,0,1);//染色過程if(color[0].size()>color[1].size())swap(color[0],color[1]);//然后白色為少的 for(int i=0;i<color[0].size();i++)//對于白色 {int v=color[0][i];ans[v]=(1ll<<60)-1-(1ll<<59)-(1ll<<i);id[v]=i;}for(int i=0;i<color[1].size();i++){int u=color[1][i];ll tmp=(1ll<<59);//首位是1for(auto v:g[u]){tmp+=(1ll<<id[v]);//與第v位相連，該點編號是id[v] } ans[u]=tmp;id[u]=i;}for(int i=1;i<=n;i++)if(i==1) printf("%lld",ans[i]);else printf(" %lld",ans[i]); }

總結

以上是生活随笔為你收集整理的Tree Constructer的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。