Codeforces739 B.Alyona and a tree(倍增+树上差分)

    科技2022-07-13  124

    题意:

    给定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; }
    Processed: 0.010, SQL: 8