题意:
给定n个点的树,树根为1,每个点有点权a(i),每条边有边权, 对于点x,设x子树内的子节点为v,如果dist(x,v)<=a(v),那么x可以支配v。
现在要求你计算每个点能支配多少个点。
数据范围:n<=2e5,a(i)<=1e9
解法:
考虑每个点v可以被多少个x支配, 支配v的点一定是v上面的若干个点(v的祖先)
考虑对于点v,将所有支配v的点x都做一次ans[x]++, 因为支配v的点一定是v上面的一条链,树上路径加法可以用树上差分实现。
那么现在问题变为如何找到最高的x,满足x可以支配v, 可以用倍增做,预处理每个点到根节点的dist(i),倍增找到最高的合法x就行了。
code:
#include<bits/stdc++.h>
using namespace std
;
#define int long long
#define PI pair<int,int>
const int maxm
=2e5+5;
const int mod
=1e9+7;
vector
<PI
>g
[maxm
];
int f
[maxm
][25];
const int maxd
=20;
int dist
[maxm
];
int ans
[maxm
];
int a
[maxm
];
int n
;
void solve(int x
){
int p
=x
;
for(int i
=maxd
;i
>=0;i
--){
if(f
[p
][i
]&&dist
[x
]-dist
[f
[p
][i
]]<=a
[x
]){
p
=f
[p
][i
];
}
}
ans
[f
[x
][0]]++;
ans
[f
[p
][0]]--;
}
void dfs(int x
,int fa
){
for(int i
=1;i
<=maxd
;i
++){
f
[x
][i
]=f
[f
[x
][i
-1]][i
-1];
}
solve(x
);
for(auto i
:g
[x
]){
int v
=i
.first
,w
=i
.second
;
dist
[v
]=dist
[x
]+w
;
f
[v
][0]=x
;
dfs(v
,x
);
ans
[x
]+=ans
[v
];
}
}
signed main(){
cin
>>n
;
for(int i
=1;i
<=n
;i
++)cin
>>a
[i
];
for(int i
=2;i
<=n
;i
++){
int fa
,c
;cin
>>fa
>>c
;
g
[fa
].push_back({i
,c
});
}
dfs(1,1);
for(int i
=1;i
<=n
;i
++){
cout
<<ans
[i
]<<' ';
}
return 0;
}