CF 381(2) D. Alyona and a tree 好题
题意：一棵树，每个点有权值ai，每条边有边权wi。对于两点u,v，当且仅当v是u的子孙且dis(u,v)<=av，称u控制v。求每个点控制有多少个点。
题解：dis(u,v)<=av转化为dis(r,u)>=dis(r,v)-av。然后按dfs序搜索，模拟栈操作，在栈中的点肯定是在同一条链上。当搜索到ai这个点，二分查找一下栈中哪一段点满足，给这一段点加1。这里用线段树维护很麻烦，可以像一维数组一样维护，比如数组c[]，区间(l,r)要加1，只要再用一个数组f[]标记，f[l]+=1，f[r+1]-=1，计算时s[i]=s[i-1]+f[i]。
注： 1、首先要想到根据dfs序模拟出栈操作，并且在dfs时一直都是一条链。 2、二分用函数时有点纠结，以后用二分函数时应该慢一点，要特别注意范围、首尾点以及从0还是从1开始。 3、在树上像一维数组一样维护有点难想。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define FF(i,a,b) for (int i=a;i<=b;i++) #define F(i,b,a) for (int i=b;i>=a;i--) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f typedef long long ll; const int N = 2e5+10; struct Edge{ int to, w, next; }edge[N]; int n, a[N], cnt[N], ans[N], k, tot, head[N]; ll dis[N], sum; void Addedge(int u, int v, int w) { edge[tot].to=v; edge[tot].w=w; edge[tot].next=head[u]; head[u]=tot++; } void dfs(int u, int e) { if(u!=1) k++, dis[k]=dis[k-1]+edge[e].w; for(int i=head[u]; i!=-1; i=edge[i].next) { dfs(edge[i].to, i); } if(k-1>=0) cnt[k-1]+=cnt[k]; ans[u]=cnt[k]; int m=lower_bound(dis, dis+k+1, dis[k]-a[u])-dis; //注意 if(m-1>=0) cnt[m-1]--; if(k-1>=0) cnt[k-1]++; cnt[k]=dis[k]=0; //退栈时注意清0，后面可能还要用到 k--; } int main() { scanf("%d", &n); FF(i,1,n) scanf("%d", &a[i]); mes(head, -1); FF(i,2,n) { int pi, wi; scanf("%d%d", &pi, &wi); Addedge(pi, i, wi); } k=0, dis[0]=0; mes(ans, 0); mes(cnt, 0); dfs(1,head[1]); FF(i,1,n) printf("%d ", ans[i]); return 0; }