1. 首頁 > 生活百科 > >

Codeforces 1670 E. Hemose on the Tree

生活百科

題意給你個數p，n = 2^p；有一棵樹有n個節點,告訴你怎么連邊；每個點有個權值，每條邊也有個權值，權值需要自行分配，[1,2,3..n...2n-1]，總共2n-1個權值；你需要選一個節點 ， 使得他到所有其他邊或者節點的簡單路徑的異或最大值最小 。
思路顯然，給你個p，不直接給你n一定是有潛藏的東西的 ， 分析一下,n = 2^p, 那么n 的結構一定是 1 000000 ,1后面都是0，那可以推測出最終的答案一定是小于等于n的

Codeforces 1670 E. Hemose on the Tree

文章插圖
1. 初始節點可以隨便選的，但是它的值一定設為n2. 處于一個點的連接點與邊來說 ， 他們的關系一定是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】

    推薦閱讀