2018牛客国庆集训派对Day1 D-Love Live! （01字典数+树上启发式合并/静态链分治）
链接：https://ac.nowcoder.com/acm/contest/201/D
来源：牛客网
Love Live!
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 1048576K，其他语言2097152K
64bit IO Format: %lld
题目描述
因为招生办的招生政策变化，Otonokizaka Academy的ACM-ICPC team面临废队危机。Honoka Kosaka,Kotori Minami,Umi Sonoda等人决定成为偶像来吸引更多的学生参加ICPC。
Honoka决定选取一些动作来编舞。我们把所有可以选择的动作用一棵 n 个点的树上的边表示，其中树的定义是无环的无向联通图。树上的每条边有一个边权 w(1 ≤ w < n)，且所有边的边权是互不相同的。如果两条边没有公共节点，就代表它们对应的动作差异很大，没有办法连续做出。又因为每个动作只能在
舞蹈中出现一次，所以能组成一支舞蹈的一套动作一定对应着树上的一条简单路径。
此外，舞蹈的优美度定义为其路径上所有边的边权异或和，难度定义为路径上所有边的边权最大值。
Honoka想知道对于[1, n) 的每种难度，最优美的舞蹈的优美度是多少。
输入描述:
输入第一行一个正整数 n(2 ≤ n ≤ 105)。
接下来 n-1 行，每行三个正整数 u,v,w(1≤ u,v ≤ n, 1≤ w < n) 表示点 u 和点 v 之间有一条边权为 w 的边。
保证输入的图可以构成一棵树，且所有边的边权互不相同。
输出描述:
一行 n-1 个整数，第 i 个数表示所有难度为 i 的舞蹈中最大的优美度。
示例1
输入
[复制](javascript:void(0)😉
7
1 2 4
1 3 3
2 4 1
2 5 2
3 6 5
3 7 6
输出
[复制](javascript:void(0)😉
1 3 3 7 6 6
思路：
前置知识1：
设\(dis(i,j)\)是树上i到j节点简单路径上的权值异或和。
那么\(dis(i,j)=dis(1,i) \oplus dis(1,j)\)
所以我们建树后dfs可以获得\(pre[i]\)代表从根节点到节点i简单路径上的权值异或和。
那么\(dis(i,j)=pre[i] \oplus pre[j]\)
前置知识2：
会用01字典树处理一个正整数x与一个整数集合\(S\)中哪个数异或值最大。
我们按照边权升序来对边进行排序，
然后从最小的边权边逐一来处理得出答案，过程如下：
用并查集查出边\(e_i\)的2个节点分别在的集合编号。
设x=将其中集合大小较小的那一个，y=将其中集合大小较大的那一个。
将集合x中的所有\(pre[i]\),放入集合y的所有\(pre[j]\)建立的01字典数中查询可以异或得出的最大值。同时维护字典树返回的最大值，就是路径中边权最大值为\(e_i.w\)的答案。
然后将集合x中的所有\(pre[i]\),放入集合y中，并将并查集中x的父节点设为y（即在dsu中合并集合）。
正确性：因为边权按升序来处理的，所以已经在集合中的边权都是小于当前边权的。
时间复杂度：
因为每一次遍历的都是集合中较小的那个，
所以遍历的总次数极端情况为：\(\sum _{i=2}^n \frac{n}{i} = n*\sum _{i=2}^n \frac{1}{i} \leq n*\sum _{i=1}^n \frac{1}{i}\)
\(\sum _{i=1}^n \frac{1}{i}\)为调和级数，所以\(n*\sum _{i=1}^n \frac{1}{i} \leq n*log(n)\)
每一次遍历的时候又用01字典树处理异或最大值，所以总的时间复杂度为：
\(O(n*log(n)^2 )\)
代码：
/*** TEMPLATE CODE * * STARTS HERE ***/
int far[maxn];
int dsu_sz[maxn];
void dsu_init(int n)
{
repd(i, 0, n)
{
far[i] = i;
dsu_sz[i] = 1;
}
}
int findpar(int x)
{
if (x == far[x])
{
return x;
} else
{
return far[x] = findpar(far[x]);
}
}
void mg(int x, int y)
{
x = findpar(x);
y = findpar(y);
if (dsu_sz[x] > dsu_sz[y])
{
dsu_sz[x] += dsu_sz[y];
far[y] = x;
} else
{
dsu_sz[y] += dsu_sz[x];
far[x] = y;
}
}
struct node
{
int u, v, w;
node() {}
node(int uu, int vv, int ww)
{
u = uu;
v = vv;
w = ww;
}
bool operator < (const node & b )const
{
return w < b.w;
}
} e[maxn];
int n;
std::vector<pii> son[maxn];
int pre[maxn];
void dfs(int x, int prev)
{
for (auto y : son[x])
{
if (y.fi == prev)
continue;
pre[y.fi] = (pre[x] ^ y.se);
dfs(y.fi, x);
}
}
std::vector<int> info[maxn];
#define bitlen 20
struct Trie
{
int ch[maxn * 100][2];
int cnt;
void init(int num)
{
cnt = num;
memset(ch, 0, sizeof(ch));
}
void insert(int rt, int x)
{
bitset<bitlen> bit;
bit = x;
for (int i = bitlen - 1; i >= 0; --i)
{
int id = bit[i];
if (!ch[rt][id])
{
ch[rt][id] = ++cnt;
}
rt = ch[rt][id];
}
}
int ask(int rt, int x)
{
int res = 0;
bitset<bitlen> bit;
bit = x;
for (int i = bitlen - 1; i >= 0; --i)
{
int id = bit[i];
if (ch[rt][ id ^ 1])
{
rt = ch[rt][id ^ 1];
res += (1 << i);
} else
{
rt = ch[rt][id];
}
}
return res;
}
} trie;
int main()
{
//freopen("D:\\code\\text\\input.txt","r",stdin);
//freopen("D:\\code\\text\\output.txt","w",stdout);
n = readint();
repd(i, 1, n - 1)
{
e[i].u = readint();
e[i].v = readint();
e[i].w = readint();
son[e[i].u].push_back(mp(e[i].v, e[i].w));
son[e[i].v].push_back(mp(e[i].u, e[i].w));
}
pre[1] = 0;
dfs(1, 0);
dsu_init(n);
trie.init(n);
repd(i, 1, n)
{
info[i].push_back(pre[i]);
trie.insert(i, pre[i]);
}
sort(e + 1, e + n);
repd(i, 1, n - 1)
{
int x = e[i].u;
int y = e[i].v;
x = findpar(x);
y = findpar(y);
if (dsu_sz[x] > dsu_sz[y])
{
swap(x, y);
}
int ans = 0;
for (auto t : info[x])
{
ans = max(ans, trie.ask(y, t));
}
for (auto t : info[x])
{
trie.insert(y, t);
info[y].push_back(t);
}
mg(x, y);
printf("%d%c", ans, i == n ? '\n' : ' ');
}
return 0;
}
京公网安备 11010502036488号