题目大意
给出一个 N 个点的树和$K_i$， 求每个点到其他所有点距离中第 $K_i$ 小的数值。
题目分析
做法一：点分树上$\log^3$
首先暴力做法：对于每个节点维护其他点距离的值域线段树。这个做法的瓶颈在于关于边$(u,v)$线段树的转移。那么可以利用点分树（为了保证复杂度）换一种容斥的思路利用重复的信息：记$f_i$为以$i$为根的点分树内所有其他点到点$i$的距离的值域线段树；$g_i$为以$i$为根的点分树内，所有点到$i$的点分树父亲的距离 的值域线段树。
询问的时候，记$LIM$为二分的长度，查询点为$pos$，$lst$的点分树父亲为$i$，那么每一层的贡献就是$f_i$中$LIM-dis(pos,i)$减去$g_{lst}$中$LIM-dis(pos,i)$的代价，注意还要特判一下$(pos,i)$这条路径是否会被算入贡献。
#include<bits/stdc++.h>
const int maxLog = ;
const int maxn = ;
const int maxm = ;
const int maxNode = ; struct node
{
int l,r,val;
};
int LIM;
struct RangeSeg
{
int tot,rt[maxn];
node a[maxNode];
void modify(int &rt, int l, int r, int pos)
{
if (!rt) rt = ++tot;
++a[rt].val;
if (l==r) return;
int mid = (l+r)>>;
if (pos <= mid) modify(a[rt].l, l, mid, pos);
else modify(a[rt].r, mid+, r, pos);
}
int query(int rt, int L, int R, int l, int r)
{
if (!rt) return ;
if (L <= l&&r <= R) return a[rt].val;
int mid = (l+r)>>, ret = ;
if (L <= mid) ret = query(a[rt].l, L, R, l, mid);
if (R > mid) ret += query(a[rt].r, L, R, mid+, r);
return ret;
}
void modify(int x, int c)
{
modify(rt[x], , LIM, c);
}
int query(int x, int l, int r)
{
if (l <= r) return query(rt[x], l, r, , LIM);
else return ;
}
}f,g;
int n,k[maxn];
int dep[maxn],fat[maxn][maxLog],lay[maxn];
int size[maxn],bloTot,son[maxn],root;
int edgeTot,head[maxn],nxt[maxm],edges[maxm];
bool vis[maxn]; int read()
{
char ch = getchar();
int num = , fl = ;
for (; !isdigit(ch); ch=getchar())
if (ch=='-') fl = -;
for (; isdigit(ch); ch=getchar())
num = (num<<)+(num<<)+ch-;
return num*fl;
}
void addedge(int u, int v)
{
edges[++edgeTot] = v, nxt[edgeTot] = head[u], head[u] = edgeTot;
edges[++edgeTot] = u, nxt[edgeTot] = head[v], head[v] = edgeTot;
}
int lca(int x, int y)
{
if (dep[x] > dep[y]) std::swap(x, y);
for (int i=; i>=; i--)
if (dep[fat[y][i]] >= dep[x]) y = fat[y][i];
if (x==y) return x;
for (int i=; i>=; i--)
if (fat[x][i]!=fat[y][i]) x = fat[x][i], y = fat[y][i];
return fat[x][];
}
int dist(int x, int y){return dep[x]+dep[y]-(dep[lca(x, y)]<<);}
void dfs(int x, int fa)
{
fat[x][] = fa, dep[x] = dep[fa]+;
for (int i=; i<=; i++)
fat[x][i] = fat[fat[x][i-]][i-];
for (int i=head[x]; i!=-; i=nxt[i])
if (edges[i]!=fa) dfs(edges[i], x);
}
void getRoot(int x, int fa)
{
size[x] = , son[x] = ;
for (int i=head[x]; i!=-; i=nxt[i])
{
int v = edges[i];
if (v==fa||vis[v]) continue;
getRoot(v, x);
size[x] += size[v];
son[x] = std::max(son[x], size[v]);
}
son[x] = std::max(son[x], bloTot-size[x]);
if (son[x] < son[root]) root = x;
}
void color(int Top, int x, int fa)
{
if (Top!=x) f.modify(Top, dist(Top, x));
if (lay[Top]) g.modify(Top, dist(lay[Top], x));
for (int i=head[x]; i!=-; i=nxt[i])
if (edges[i]!=fa&&!vis[edges[i]]) color(Top, edges[i], x);
}
void deal(int x, int pre)
{
lay[x] = pre, color(x, x, x), vis[x] = true;
for (int i=head[x]; i!=-; i=nxt[i])
{
int v = edges[i];
if (vis[v]) continue;
bloTot = size[v], root = , getRoot(v, );
deal(root, x);
}
}
int count(int x, int num)
{
int ret = f.query(x, , num);
for (int i=lay[x],lst=x; i; lst=i,i=lay[i])
{
int d = dist(x, i);
if (d <= num) ++ret, ret += f.query(i, , num-d)-g.query(lst, , num-d);
}
return ret;
}
int main()
{
memset(head, -, sizeof head);
LIM = n = read();
for (int i=; i<=n; i++) k[i] = n-read();
for (int i=; i<n; i++) addedge(read(), read());
dfs(, );
bloTot = n, root = , son[] = n, getRoot(, );
deal(root, );
for (int i=; i<=n; i++)
{
int L = , R = LIM, ans = ;
for (int mid=(L+R)>>; L<=R; mid=(L+R)>>)
if (count(i, mid) < k[i]) L = mid+, ans = mid;
else R = mid-;
printf("%d ",ans);
}
return ;
}
做法二：序列问题分块
不说了。类似的套路见#6046. 「雅礼集训 2017 Day8」爷