B. Alyona and a tree(思维+倍增/二分+树上差分)

163 阅读 0 评论 108 点赞

我是靠谱客的博主甜美短靴，这篇文章主要介绍B. Alyona and a tree(思维+倍增/二分+树上差分)，现在分享给大家，希望可以做个参考。

https://codeforces.com/problemset/problem/739/B

思路：

对于题目的条件，转化成对于某个点，其有多少点能控制它。朴素就是每个点网上跳对于每个点能更新的更新，不能更新意味着break。O（n^2)

break意味着其条件满足单调性，于是可以树上二分能到的最远的祖先，当然了，倍增也是同样的道理，其二进制能表示出最远的祖先。

然后对于起点到祖先的一段区间，我们可以直接+1，树上差分比较方便(当然你硬要写个树剖再多个log.....也无话说

对于求带边权的两点距离，转化到起点的前缀和，由于此题是往祖先跳的，都在一个链中，所以不需要LCA，单纯倍增就好。剩下log。

复制代码

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=2e5+1000;
typedef long long LL;
inline LL read(){LL x=0,f=1;char ch=getchar();	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;}
LL fa[maxn][22],dep[maxn];
LL a[maxn],dif[maxn];
LL dis[maxn];///所有点到起点的距离
struct Edge{
   LL to,val;
};
vector<Edge>g[maxn];
void dfs1(LL u,LL father,LL c){
     dep[u]=dep[father]+1;
     fa[u][0]=father;
     dis[u]=dis[father]+c;
     for(LL i=1;(1<<i)<=dep[u];i++){
         fa[u][i]=fa[fa[u][i-1]][i-1];
     }
     for(LL i=0;i<g[u].size();i++){
         LL v=g[u][i].to;
         dfs1(v,u,g[u][i].val);
     }
}
void solve(LL now){
     LL x=now;
     for(LL i=20;i>=0;i--){
         if(fa[x][i]&&dis[now]-dis[fa[x][i]]<=a[now]) x=fa[x][i];
     }
     if(x!=1) dif[fa[x][0]]--;
     if(now!=1) dif[fa[now][0]]++;
}
LL dfs2(LL u){
     for(LL i=0;i<g[u].size();i++){
         LL v=g[u][i].to;
         dif[u]+=dfs2(v);
     }
     return dif[u];
}
int main(void){
   LL n;n=read();
   for(LL i=1;i<=n;i++) cin>>a[i];
   for(LL i=2;i<=n;i++){
       LL f,cost;cin>>f>>cost;
       g[f].push_back({i,cost});///单向边
   }
   dfs1(1,0,0);
   for(LL i=1;i<=n;i++) solve(i);
   dfs2(1);
   for(LL i=1;i<=n;i++) cout<<dif[i]<<" ";
   cout<<"n";
   return 0;
}

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
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=2e5+1000;
typedef long long LL;
inline LL read(){LL x=0,f=1;char ch=getchar();	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;}
LL fa[maxn][22],dep[maxn];
LL a[maxn],dif[maxn];
LL dis[maxn];///所有点到起点的距离
struct Edge{
   LL to,val;
};
vector<Edge>g[maxn];
void dfs1(LL u,LL father,LL c){
     dep[u]=dep[father]+1;
     fa[u][0]=father;
     dis[u]=dis[father]+c;
     for(LL i=1;(1<<i)<=dep[u];i++){
         fa[u][i]=fa[fa[u][i-1]][i-1];
     }
     for(LL i=0;i<g[u].size();i++){
         LL v=g[u][i].to;
         dfs1(v,u,g[u][i].val);
     }
}
void solve(LL now){
     LL x=now;
     for(LL i=20;i>=0;i--){
         if(fa[x][i]&&dis[now]-dis[fa[x][i]]<=a[now]) x=fa[x][i];
     }
     if(x!=1) dif[fa[x][0]]--;
     if(now!=1) dif[fa[now][0]]++;
}
LL dfs2(LL u){
     for(LL i=0;i<g[u].size();i++){
         LL v=g[u][i].to;
         dif[u]+=dfs2(v);
     }
     return dif[u];
}
int main(void){
   LL n;n=read();
   for(LL i=1;i<=n;i++) cin>>a[i];
   for(LL i=2;i<=n;i++){
       LL f,cost;cin>>f>>cost;
       g[f].push_back({i,cost});///单向边
   }
   dfs1(1,0,0);
   for(LL i=1;i<=n;i++) solve(i);
   dfs2(1);
   for(LL i=1;i<=n;i++) cout<<dif[i]<<" ";
   cout<<"n";
   return 0;
}