点击打开链接
题意:n个结点,带权的树,v控制u当且仅当 u为v的子孙&& dist[u,v]<=a[u],n<=2e5,问每个结点控制的数量?
设d[i]为i->rt的距离,dist[u,v]=d[u]-d[v],根据u来更新答案,控制u的v必须满足 ,d[v]>=d[u]-a[u] d[i]随着深度递增,若在dfs过程中保存u的祖先的d值,可以二分找到第一个满足的pos,则ans[pos~fa[u]]都应该+1
怎么判断祖先v被加了多少次?
回顾:[l,r]内的数都+1,则a[l]++,a[r+1]--,问a[i]的值,只要求出a[i]的前缀和即可(不包含a[i]的[l,r] l..r..i在累加前缀时被抵消)
sum[pos~fa[u]]+1,在树上进行差分:让sum[fa[pos]]--,sum[fa[u]]++,问v被加了多少次? 只要累加v的子树的sum,(v不在某个u的[pos~fa[u],则累加时,该段sum被抵消)
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> ii; const int N=4e5+20; ll a[N],sum[N],d[N],n; vector<ii> e[N];//w,v vector<ii> que; void dfs(int u,int fa) { sum[fa]++; ll t=d[u]-a[u]; int pos=lower_bound(que.begin(),que.end(),ii(t,0))-que.begin(); pos--;//fa[pos] if(pos>=0) sum[que[pos].second]--; que.push_back(ii(d[u],u)); for(int i=0;i<e[u].size();i++) { ll v=e[u][i].second,w=e[u][i].first; if(v==fa) continue; d[v]=d[u]+w; dfs(v,u); sum[u]+=sum[v];// } que.pop_back();//u不在为任何结点的祖先 } int main() { while(cin>>n) { for(int i=1;i<=n;i++) scanf("%I64d",&a[i]),e[i].clear(),sum[i]=0,d[i]=0; ll p,w; for(int i=2;i<=n;i++) { scanf("%I64d%I64d",&p,&w); e[i].push_back(ii(w,p)); e[p].push_back(ii(w,i)); } dfs(1,0); for(int i=1;i<=n;i++) printf("%I64d%c",sum[i],i==n?'\n':' '); } return 0; }
