题意

给你个数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;

}

巴特西

Codeforces 1670 E. Hemose on the Tree

题意

思路

代码

最新文章

热门文章