题目大意：
给出一棵n 个节点的树，每条边有一个权值
若v 在u 的子树内，且，则称u 能控制v
问每个点能控制多少点
因为v 在u 的子树内，所以
化简得
观察到为定值，且单调递增
找到第一个点u，满足，则路径上所有点均可控制点
由于只有一次询问，可用树上差分
至于怎么找第一个满足的点u，可以用二分或倍增
感觉倍增实现起来会简单一点，代码用的是二分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
using namespace std;
const int N=200050,rt=1;
int n,w[N],cnt[N],fa[N];
LL dep[N];
vector<int> e[N],g[N],Q;
inline int read()
{
register int x=0,t=1;
register char ch=getchar();
while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if (ch=='-') t=-1,ch=getchar();
while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
void add(int u,int v,int val)
{
e[u].push_back(v);
g[u].push_back(val);
}
int find(LL key)
{
if (Q.empty()) return 0;
if (dep[Q.back()]<key) return Q.back();
int L=0,R=Q.size()-1;
while (L<R)
{
int mid=(L+R)>>1;
if (dep[Q[mid]]<key)
L=mid+1;
else
R=mid;
}
return Q[R];
}
void dfs(int o,int pre)
{
if (!Q.empty()&&dep[o]-w[o]<=dep[Q.back()])
{
cnt[fa[find(dep[o]-w[o])]]--;
cnt[fa[o]]++;
}
Q.push_back(o);
for(int i=0;i<e[o].size();i++)
{
int to=e[o][i];
if (to!=pre)
{
dep[to]=dep[o]+g[o][i];
fa[to]=o;
dfs(to,o);
}
}
Q.pop_back();
}
void calc(int o)
{
for(int i=0;i<e[o].size();i++)
{
int to=e[o][i];
if (dep[to]>dep[o])
{
calc(to);
cnt[o]+=cnt[to];
}
}
}
int main()
{
n=read();
for(int i=1;i<=n;i++) w[i]=read();
for(int u=2;u<=n;u++)
{
int v=read(),val=read();
add(u,v,val);
add(v,u,val);
}
dfs(rt,0),calc(rt);
for(int i=1;i<=n;i++) printf("%d ",cnt[i]);
return 0;
}