題意
給你個數p，n = 2^p；
有一棵樹有n個節點,告訴你怎么連邊；
每個點有個權值，每條邊也有個權值，權值需要自行分配，[1,2,3..n...2n-1]，總共2n-1個權值；
你需要選一個節點，使得他到所有其他邊或者節點的簡單路徑的異或最大值最小，
思路
顯然，給你個p，不直接給你n一定是有潛藏的東西的，分析一下,n = 2^p, 那么n 的結構一定是 1 000000 ,1后面都是0，那可以推測出最終的答案一定是小于等于n的
1. 初始節點可以隨便選的，但是它的值一定設為n
2. 處于一個點的連接點與邊來說，他們的關系一定是x，x+n，這樣他們的異或值一定是n，可以保證答案在0-n之間改變，注意x與x+n的位置設定
3. 如果不這樣構造，最高位是1的情況下，一定不優于這種構造
代碼
#include<bits/stdc++.h>
using namespace std;
int n, p, st;
vector<pair<int, int>> g[300005];
int ans[300005], w[300005];
void dfs(int x, int fa, int pre) {
for (auto k: g[x]) {
if (k.first == fa)continue;
st++;
if ((st ^ pre) <= n) {
w[k.second] = st;
ans[k.first] = st + n;
} else {
w[k.second] = st + n;
ans[k.first] = st;
}
dfs(k.first, x, pre ^ n);
}
}
void run() {
cin >> p;
n = 1 << p;
for (int i = 1; i <= n; i++)g[i].clear();
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
g[x].push_back(make_pair(y, i));
g[y].push_back(make_pair(x, i));
}
st = 0;
ans[1] = n;
dfs(1, 0, n);
cout << 1 << '\n';
for (int i = 1; i <= n; i++)cout << ans[i] << " \n"[i == n];
for (int i = 1; i < n; i++)cout << w[i] << " \n"[i == n - 1];
}
int main() {
int t;
cin >> t;
while (t--)
run();
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/524973.html
標籤：其他
上一篇：主定理