首先处理出 \(f_i\) 表示 \(i\) 向上一小时最多走到什么地方。
由于边权只有 \(1,2\)，这个可以树上双指针 \(O(n)\)。
询问时，显然应当跳 \(f_i\) 到一个最浅的深于 LCA 的点，然后考虑最后这一段路程是否超过 \(D\)。
然而倍增是卡不过的，考虑离线，Tarjan 求 LCA 并把询问记录在 LCA 上。
注意到可以利用 Tarjan 类似的思路，用并查集来维护这个能跳到的最浅点，而利用回溯时的更新保证不会跳到 LCA 或以上。
同时需要记录步数，这个是带权并查集基本操作（
代码： 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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
using namespace std;
const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
template<class T>
inline void read(T &x)
{
x = 0;
char ch = 0,w = 0;
for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
w && (x = -x);
}
const int N = 5e5;
int n,d,q;
namespace EDGE
{
int to[N + 5],pre[N + 5],first[N + 5];
inline void add(int u,int v)
{
static int tot = 0;
to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
}
int fa[N + 5],a[N + 5];
int f[N + 5],s[N + 5];
int ans[N + 5];
namespace QUERY
{
int x[N + 5],y[N + 5],pre[N + 5],first[N + 5],id[N + 5];
inline void add(int lca,int u,int v,int i)
{
static int tot = 0;
x[++tot] = u,y[tot] = v,id[tot] = i,pre[tot] = first[lca],first[lca] = tot;
}
}
namespace TAR1
{
int to[(N << 1) + 5],pre[(N << 1) + 5],id[(N << 1) + 5],first[N + 5];
int done[N + 5];
inline int init()
{
memset(first,-1,sizeof first);
return 0;
}
int Init = init();
inline void add(int u,int v,int i)
{
static int tot = 0;
to[tot] = v,id[tot] = i,pre[tot] = first[u],first[u] = tot++;
}
int fa[N + 5],vis[N + 5];
int get(int x)
{
return !fa[x] ? x : (fa[x] = get(fa[x]));
}
void dfs(int p)
{
vis[p] = 1;
for(register int i = EDGE::first[p];i;i = EDGE::pre[i])
dfs(EDGE::to[i]),fa[EDGE::to[i]] = p;
for(register int i = first[p];~i;i = pre[i])
vis[to[i]] && !done[id[i]] && (QUERY::add(get(to[i]),p,to[i],id[i]),done[id[i]] = 1);
}
}
namespace TAR2
{
int to[N + 5],pre[N + 5],first[N + 5];
inline void add(int u,int v)
{
static int tot = 0;
to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
int fa[N + 5],cnt[N + 5],vis[N + 5];
int get(int x)
{
if(!fa[x])
return x;
int f = fa[x];
fa[x] = get(f),cnt[x] += cnt[f];
return fa[x];
}
void dfs(int p)
{
vis[p] = 1;
for(register int i = EDGE::first[p];i;i = EDGE::pre[i])
dfs(EDGE::to[i]);
for(register int i = QUERY::first[p],x,y,u,v;i;i = QUERY::pre[i])
{
u = get(x = QUERY::x[i]),v = get(y = QUERY::y[i]);
ans[QUERY::id[i]] = cnt[x] + cnt[y] + (x != y) + (s[u] + s[v] - (s[p] << 1) > d);
}
for(register int i = first[p];i;i = pre[i])
fa[to[i]] = p,cnt[to[i]] = 1;
}
}
int main()
{
freopen("mancity.in","r",stdin),freopen("mancity.out","w",stdout);
read(n),read(d),read(q),f[1] = 1;
for(register int i = 2;i <= n;++i)
read(fa[i]),read(a[i]),s[i] = s[fa[i]] + a[i],f[i] = i,EDGE::add(fa[i],i);
for(register int p = n;p;--p)
{
for(;fa[f[p]] && s[p] - s[fa[f[p]]] <= d;f[p] = fa[f[p]]);
TAR2::add(f[p],p),f[fa[p]] = min(f[fa[p]],f[p]);
}
int u,v;
for(register int i = 1;i <= q;++i)
read(u),read(v),TAR1::add(u,v,i),TAR1::add(v,u,i);
TAR1::dfs(1),TAR2::dfs(1);
for(register int i = 1;i <= q;++i)
printf("%d\n",ans[i]);
}