题意

给你个数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的情况下,一定不优于这种构造

代码

#includeusing namespace std;int n, p, st;vector<pair> 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) > p;    n = 1 << p;    for (int i = 1; i <= n; i++)g[i].clear();    for (int i = 1; i > 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] <> t;    while (t--)        run();    return 0;}