洛谷P3899题解 【[湖南集训]谈笑风生】

有巨佬说这题亦可赛艇，确实挺亦可赛艇（

$\texttt{Desciption}$

我觉得题面挺简洁的，至少没有废话，所以直接传送门

$\texttt{Solution}$

方法一：

首先，当 $b$ 是 $a$ 的祖先时，$c$ 有 $cnt_a$ 种情况（$cnt_u$ 表示 $u$ 所有子节点个数（不包括 $u$ 自己））。而 $b$ 有 $min(k,dep_a)$ 种情况（$dep_u$ 表示 $u$ 的深度），所以一共有 $min(k,dep_a)\times cnt_a$ 种情况。

当 $a$ 是 $b$ 的祖先时，$b$ 需要满足以下条件：

• 是 $a$ 的子节点（废话）
• $dep_b-dep_a\le k$

考虑对于每个节点都建一颗线段树，以深度作为下标，则我们需要查询 $[dep_a,dep_a+k]$ 区间的贡献。每个节点的贡献是它的 $cnt$ 值。

那么就成了线段树合并的题了。线段树合并如果直接在原子树合并就是离线的，时空常数小，新建节点就是在线的，时空常数大。

方法二：

当 $a$ 是 $b$ 的祖先时，该方法处理与方法一不同。

$b$ 是 $a$ 的子节点这个条件，方法一是直接给每个节点建了一颗线段树，但我们可以想到，判断 $b$ 是否是 $a$ 子节点可以 dfs 序。为了方便描述，$In_u$ 表示第一次访问 $u$ 时的时间戳，$Out_u$ 表示回溯到 $u$ 时的时间戳。

则点 $b$ 需要满足以下条件：

• $In_a\le In_b\le Out_a$
• $dep_b-dep_a\le k$

那这不就是一个二维偏序问题了？离线BIT处理即可。

两种方法时间复杂度均为 $O(nlogn)$

$\texttt{Code}$

只写了方法一。写完了发现BIT可以做口胡的第二种做法。

#include <cstdio>
#include <vector>
#define int long long
#define getl(p) (ls[p] ? ls[p] : ls[p] = ++ tot)
#define getr(p) (rs[p] ? rs[p] : rs[p] = ++ tot)

inline int min(const int x, const int y) {return x < y ? x : y;}
struct Edge {
	int to, nxt;
} e[600005];
int ls[3000005], rs[3000005], v[3000005], root[300005], tot, tot2;
int Dep[300005], head[300005], cnt[300005], ans[300005], n;
struct Node {
	int id, k;
};
std::vector<Node> ques[300005];
inline void AddEdge(const int u, const int v) {
	e[++ tot2].to = v, e[tot2].nxt = head[u], head[u] = tot2;
}

void update(const int O, const int x, const int d, const int l, const int r) {
	if (l == r) {v[O] += d; return;}
	const int mid(l + r >> 1);
	if (x <= mid) update(getl(O), x, d, l, l + r >> 1);
	else update(getr(O), x, d, (l + r >> 1) + 1, r);
	v[O] = v[ls[O]] + v[rs[O]];
}
int query(const int O, const int L, const int R, const int l, const int r) {
	if (L <= l && r <= R) return v[O];
	const int mid(l + r >> 1);
	int ans(0);
	if (L <= mid && ls[O]) ans += query(ls[O], L, R, l, mid);
	if (mid < R && rs[O]) ans += query(rs[O], L, R, mid + 1, r);
	return ans;
}
void merge(int& x, const int y) {
	if (!x || !y) {x |= y; return;}
	v[x] += v[y];
	merge(ls[x], ls[y]);
	merge(rs[x], rs[y]);
}
void dfs(const int u, const int fa) {
	Dep[u] = Dep[fa] + 1;
	for (int i(head[u]); i; i = e[i].nxt) if (e[i].to != fa) {
		const int v(e[i].to);
		dfs(v, u);
		cnt[u] += cnt[v] + 1;
		merge(root[u], root[v]);
	}
	for (Node& i : ques[u]) {
		ans[i.id] = query(root[u], Dep[u], Dep[u] + i.k, 1, n);
		ans[i.id] += min(Dep[u] - 1, i.k) * cnt[u];
	}
	update(root[u], Dep[u], cnt[u], 1, n);
}
signed main() {
	int q;
	scanf("%lld%lld", &n, &q);
	for (int i(1); i < n; ++ i) {
		int u, v;
		scanf("%lld%lld", &u, &v);
		AddEdge(u, v), AddEdge(v, u);
	}
	for (int i(1); i <= n; ++ i) root[i] = i;
	tot = n;
	for (int i(1); i <= q; ++ i) {
		int p, k;
		scanf("%lld%lld", &p, &k);
		ques[p].push_back(Node{i, k});
	}
	dfs(1, -1);
	for (int i(1); i <= q; ++ i) printf("%lld\n", ans[i]);
}