传送门

显然树上第k大直接主席树

如果连边的话，我们重构小的那一棵，连到另一棵上。

说起来简单，调了我一晚上。

总的来说3个错误：

1.离散化写错位置写到了后面

2."="写成了"=="

3.加双向边时加成了单向边

3个错误3个小时。。。

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define N 80011#define M 10000000using namespace std;int n, m, T, cnt, tot, test, last;int head[N], to[N << 2], nex[N << 2], val[N], ntr[N], deep[N], f[N][21], root[N], sum[M], ls[M], rs[M], fa[N], size[N];bool vis[N];inline int read()inline void add(int x, int y)inline int find(int x)inline void Union(int x, int y)inline int query(int a, int b, int c, int d, int l, int r, int x)inline void insert(int &now, int last, int l, int r, int x)inline void dfs(int u)}vis[u] = 0;}inline int lca(int x, int y)int main()for(i = 1; i <= m; i++)sort(ntr + 1, ntr + n + 1);m = unique(ntr + 1, ntr + n + 1)  ntr  1;for(i = 1; i <= n; i++) val[i] = lower_bound(ntr + 1, ntr + m + 1, val[i])  ntr;for(i = 1; i <= n; i++)if(!deep[i]) dfs(i);while(T)else}return 0;}