cf739B Alyona and a tree

Alyona and a tree

题意

给定一棵树($n\leq 2\times 10^5$),树上的路径有权值,树上每个点有权值,称结点$u$控制$v$当且仅当$v$是$u$的子孙并且$u$到$v$简单路径的权值小于$v$的权值。问每个点在树上控制几个点

样例

sample1

1
2
3
4
5
6
5
2 5 1 4 6
1 7
1 1
3 5
3 6
1
1 0 1 0 0

sample2

1
2
3
4
5
6
5
9 7 8 6 5
1 1
2 1
3 1
4 1
1
4 3 2 1 0

题解1

不难发现对于一个点$u$,他被一些祖先控制,且这些祖先是树上这条链连续的一段。一定存在某个点,他到$u$的距离小于$u$的权值$w_u$,并且它的父亲不再控制$u$(换言之,它的父亲到$u$的距离大于$u$的点权)。因而我们考虑对每个点到其祖先的这条链上二分找到这个断点,然后更新从$u$的父亲开始一直到这个断点的答案(全部$+1$),这是可以使用树剖完成的。

复杂度1

$\mathcal O(nlog_n)$

程序1

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2*100000+5;
int head[maxn],ed[maxn*4];
ll co[maxn*4],w[maxn*4];
int nxt[maxn*4];
int cnt=0,n;
void addedge(int v,int u,ll c)
{
ed[++cnt]=u;co[cnt]=c;nxt[cnt]=head[v];head[v]=cnt;
ed[++cnt]=v;co[cnt]=c,nxt[cnt]=head[u],head[u]=cnt;
}
int pa[maxn],up[maxn];
ll siz[maxn];
ll dep[maxn];
void dfs(int v,int fa,ll precost)
{
pa[v]=fa;
dep[v]=fa==-1?0:dep[fa]+precost;siz[v]=1;
for(int i=head[v];i!=-1;i=nxt[i]){
int u=ed[i];
if(u!=fa){
dfs(u,v,co[i]);
siz[v]+=siz[u];
}
}
}
int id[maxn],reid[maxn],dfsclock=0;
void dfs2(int v,int fa,int anse)
{
id[v]=++dfsclock;
reid[dfsclock]=v;
up[v]=anse;
int tmpmax=0,tmp=0;
for(int i=head[v];i!=-1;i=nxt[i]){
int u=ed[i];
if(u!=fa && siz[u]>tmp) tmp=siz[u],tmpmax=u;
}
if(tmpmax) dfs2(tmpmax,v,anse);
for(int i=head[v];i!=-1;i=nxt[i]){
int u=ed[i];
if(u==fa || u==tmpmax) continue;
dfs2(u,v,u);
}
}
ll sumv[maxn*10],addv[maxn*10];
#define lson (o<<1)
#define rson ((o<<1)+1)
void maintain(int o,int l,int r)
{
sumv[o]=sumv[lson]+sumv[rson];
sumv[o]+=addv[o]*(r-l+1);
}
void getadd(int o,int l,int r,ll ad)
{
addv[o]+=ad;
maintain(o,l,r);
}
void pushdown(int o,int l,int r)
{
if(addv[o]){
int mid=((l+r)>>1);
getadd(lson,l,mid,addv[o]);
getadd(rson,mid+1,r,addv[o]);
addv[o]=0;
}
maintain(o,l,r);
}
void update(int o,int l,int r,int ql,int qr,ll ad)
{
if(ql>r || qr<l) return;
if(ql<=l && r<=qr) {getadd(o,l,r,ad);return;}
else{
int mid=((l+r)>>1);
pushdown(o,l,r);
if(ql<=mid) update(lson,l,mid,ql,qr,ad);
if(qr>mid) update(rson,mid+1,r,ql,qr,ad);
maintain(o,l,r);
}
}
ll Qnow(int o,int l,int r,int ql,int qr){
if(ql>r || qr<l) return 0ll;
if(ql<=l && r<=qr) {return sumv[o];}
else{
int mid=((l+r)>>1);
pushdown(o,l,r);
ll ret=0;
if(ql<=mid) ret+=Qnow(lson,l,mid,ql,qr);
if(qr>mid) ret+=Qnow(rson,mid+1,r,ql,qr);
maintain(o,l,r);
return ret;
}
}
void getadd(int u,int v)
{
while(up[u]!=up[v]){
update(1,1,n,id[up[u]],id[u],1ll);
u=pa[up[u]];
}
if(u==v) update(1,1,n,id[u],id[u],1ll);
else{
update(1,1,n,id[v],id[u],1ll);
}
}
int SIZ=0;
int pts[maxn];
void dfs3(int v,int fa)
{
int l=0,r=SIZ-1;
if(SIZ>0){
if(l==r) {
if(dep[v]-dep[fa]<=w[v]) update(1,1,n,id[fa],id[fa],1);
}else{
if(dep[v]-dep[fa]>w[v]) {}
else{
while(r-l>=1){
int mid=((l+r)>>1);
int u=pts[mid];
if(dep[v]-dep[u]<=w[v]) r=mid;
else l=mid+1;
}
getadd(fa,pts[l]);
}
}
}
pts[SIZ++]=v;
for(int i=head[v];i!=-1;i=nxt[i])
{
int u=ed[i];
if(u!=fa){
dfs3(u,v);
}
}
SIZ--;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&w[i]);
memset(head,-1,sizeof(head));
memset(nxt,-1,sizeof(nxt));
for(int i=2;i<=n;i++){
int to;ll W;
scanf("%d%lld",&to,&W);
addedge(i,to,W);
}
dfs(1,-1,0);
dfs2(1,-1,1);
dfs3(1,-1);
for(int i=1;i<=n;i++){
printf("%lld ",Qnow(1,1,n,id[i],id[i]));
}puts("");
return 0;
}

题解2

然而这题根本不需要高级数据结构来维护就可以完成…

首先对于每个点统计答案,假定每个点对他的祖先都有贡献,那么我们可以对每个点记一个答案值(通过它的儿子的答案相加而得),在统计完自身的答案后$+1$(表示对他的祖先有贡献)。考虑二分一条以$u$为结尾的链,那么$u$的贡献是在断点处断开的,在这个断点处我们对答案值$-1$即可(因为预先认为每个点对祖先有贡献,此处表示$u$点对这个断点及以上祖先没有了贡献,因为答案指是从链的下方向上方更新的)。那么我们可以先遍历一个结点的子树,此时这个结点的儿子的答案都已经更新完毕,记录下这个结点的答案即可。

复杂度2

$\mathcal O(nlog_n)$

程序2

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MP make_pair
const int maxn=2*100000+5;
vector<pair<ll,int > > g[maxn];
int n;
ll a[maxn],ans[maxn],ad[maxn];
vector<pair<ll,int > > pts;
void dfs(int v,int fa,ll now,ll precost)
{
now+=precost;
pts.push_back(MP(now,v));
int idx=upper_bound(pts.begin(),pts.end(),MP(now-a[v],-1))-pts.begin();
if(idx>0) ad[pts[idx-1].second]--;
for(int i=0;i<(int)g[v].size();i++){
int u=g[v][i].second;
if(u!=fa){
dfs(u,v,now,g[v][i].first);
ad[v]+=ad[u];
}
}
ans[v]=ad[v];
ad[v]++;
pts.pop_back();
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
int p;ll x;
for(int i=2;i<=n;i++){
scanf("%d%lld",&p,&x);
g[i].push_back(MP(x,p));
g[p].push_back(MP(x,i));
}
dfs(1,-1,0ll,0ll);
for(int i=1;i<=n;i++) printf("%lld%c",ans[i],i==n?'\n':' ');
return 0;
}