题目连接：传送门

Description

给一棵nn颗节点的树，mm次询问，每次询问给定aa,kk，求三元组(a,b,c)(a,b,c)的数量满足：

  1. aa和bb都是cc的祖先
  2. aa和bb在树上距离不超过kk
  3. a,b,ca,b,c互不相同

Constraints

n,m≤3∗105n,m \leq 3 * 10^5

Solution

显然a,b,ca,b,c在同一条链上，考虑两种情况:

  • depa>depbdep_a > dep_b

    此时答案显然为min{(depa−1),k)}∗(sizea−1)\min\{(dep_a - 1), k)\} * (size_a - 1)

  • depa<depbdep_a < dep_b

    此时即要求∑xsizex−1\sum_{x} size_x - 1 (xx满足depx≤depa+kdep_x \leq dep_a + k且xx在aa的子树内)

    那么我们只需要在dfsdfs序上二维数点(xx轴表示dfsdfs序，yy轴表示depdep,平面内点权为sizex−1size_x - 1)即可

debug：89行dep[a]+kdep[a] + k需要与MaxdepMaxdep取min

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>

#define int long long
#define x first
#define y second
#define x1 X1 
#define x2 X2
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> T read()
{
	T fl = 1, sum = 0; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
	return sum * fl;
}

const int Maxn = 300000 + 100;

int N, M;
int e, Begin[Maxn], To[Maxn << 1], Next[Maxn << 1];
int dfn[Maxn], Index, size[Maxn], dep[Maxn], Ans[Maxn], idfn[Maxn], Maxdep;

struct node
{
	int x, y, num, op;
};
vector <node> vec[Maxn];

inline void add_edge (int x, int y)
{
	To[++e] = y;
	Next[e] = Begin[x];
	Begin[x] = e;
}

inline void dfs (int x, int fa)
{
	dfn[x] = ++Index;
	idfn[Index] = x;
	size[x] = 1;
	for (int i = Begin[x]; i; i = Next[i])
	{
		int y = To[i];
		if (y == fa) continue;
		dep[y] = dep[x] + 1;
		Chkmax(Maxdep, dep[y]);
		dfs(y, x);
		size[x] += size[y];
	}
}

namespace BIT
{
#define lowbit(x) (x & (-x))
	int sum[Maxn];
	inline void add (int x, int v) { while (x <= N) sum[x] += v, x += lowbit(x); }
	inline int query (int x) { int ans = 0; while (x) ans += sum[x], x -= lowbit(x); return ans; }
}

main()
{
#ifdef hk_cnyali
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif
	N = read<int>(), M = read<int>();
	for (int i = 1; i < N; ++i)
	{
		int x = read<int>(), y = read<int>();
		add_edge (x, y); add_edge (y, x);
	}
	dep[1] = 1;
	dfs(1, 0);
	for (int i = 1; i <= M; ++i)
	{
		int a = read<int>(), k = read<int>();
		Ans[i] += min((dep[a] - 1), k) * (size[a] - 1);
		vec[dfn[a] - 1].pb((node){dep[a], min(Maxdep, dep[a] + k), i, -1});
		vec[dfn[a] + size[a] - 1].pb((node){dep[a], min(Maxdep, dep[a] + k), i, 1});
	}
	for (int i = 1; i <= N; ++i)
	{
		BIT :: add (dep[idfn[i]], size[idfn[i]] - 1);
		for (int j = 0; j < vec[i].size(); ++j)
		{
			node x = vec[i][j];
			Ans[x.num] += x.op * (BIT :: query (x.y) - BIT :: query (x.x));
		}
	}
	for (int i = 1; i <= M; ++i)
		printf("%lld\n", Ans[i]);
	return 0;
}