题 目 链 接
思维构造题,真的是难捏...
题解看这里:https://zhuanlan.zhihu.com/p/510572963
分析一下:
1. 首先,我们构造后所有路径一定都>=2^p,即最小都是2^p(证明看题解)
2. 那么问题就转换成怎么构造使得路径尽可能靠近2^p?
写一下二进制可以发现,以2^p为分界线,对于x(1~2^p),我们一定选x+2^p最优,这样可以抵消后面的位
这样一来就和树的形状无关了(一直在想树的形状...),所以我们可以把2^p作为根的权值
(1)对于当前点,前面路径为0时,则我们先排x,再排x+2^p
(2)对于当前点,前面路径为2^p,则我们先排x+2^p,再排x;这样能抵消最高位
代码技巧还是很多的...
#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<stdio.h>
#include<map>
#include<cmath>
#include<algorithm>
#include<deque>
#include<stack>
#include <unordered_map>
#define IOS ios::sync_with_stdio(false),cin.tie(0);
using namespace std;
#define pb push_back
#define coutt cout<<"------------"<<endl;
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<char, pair<int, int> > PCII;
typedef pair<int, pair<int, int> > PIII;
const int maxn = 2e5 + 7;
const int N = 2e5+7;
const int M = 1e6+7;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = 3.14159265359;
ll gcd(ll a,ll b) {return b==0 ? a : gcd(b,a%b);}
ll qmi(ll a,ll b,ll p) {ll ans = 1; while(b) { if(b & 1) ans = ans * a % p; a = a * a % p; b >>= 1; } return ans;}
vector<int> edge[maxn]; //存每个点的边
int e[maxn]; //存每条边两个点的^
int ans_no[maxn];
int ans_e[maxn];
int n,m;
void dfs(int u,int fa,int co)
{
for(auto bian : edge[u]) //枚举边
{
if(bian == fa) continue;
int v = e[bian] ^ u;
ans_e[bian] = m + n * (co ^ 1);
ans_no[v] = m + n * co;
m++;
dfs(v,bian,co^1);
}
}
void solve()
{
scanf("%d",&n);
m = 1;
n = 1 << n;
for(int i=1;i<=n;i++) edge[i].clear();
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d %d",&u,&v);
edge[u].push_back(i);
edge[v].push_back(i);
e[i] = u ^ v; //我们存边 和 异或值,那么邻点就是v = e[i] ^ u;
}
dfs(1,-1,0);
ans_no[1] = n;
cout<<1<<endl;
for(int i=1;i<=n;i++) cout<<ans_no[i]<<' ';
cout<<endl;
for(int i=1;i<n;i++) cout<<ans_e[i]<<' ';
cout<<endl;
}
int main()
{
int t;
cin>>t;
while(t--)
{
solve();
}
return 0;
}