题目链接
题意
一棵树，树上有
n
n
n个点，标号为1~n，且1是树根。然后每个点都有一个值
a
[
i
]
a[i]
a[i]，每条边也有一个权值
w
w
w，然后让你输出每个可以控制点的数目。（比如
u
u
u控制
v
v
v，即树上
u
−
>
v
u->v
u−>v的权值
d
[
u
,
v
]
<
=
a
[
v
]
d[u,v]<=a[v]
d[u,v]<=a[v]）
思路
首先比较好想的是暴力的方法。
预处理深度遍历树根到所有节点的权值，然后对每个点进行
d
f
s
dfs
dfs，结果T。
我们在脑海中想象下遍历这棵树的过程，在DFS过程中在栈中总会呈现一条树根 到 子节点的路径，我们在这条路径上进行二分查找这条路径上 满足条件的 距当前节点最远点（也就是最靠根的节点），然后这一段路径区间都可以加1，区间修改，我们可以差分来缩减时间复杂度，只不过这是在树上差分。
有一点需要注意，差分时注意区间首尾别颠倒！
A
C
C
o
d
e
:
AC Code:
AC Code:
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#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<vector> #include<iostream> using namespace std; #define ll long long #define INF 0x3f3f3f3f const ll N = 2e5+10; ll d[N];//到根节点的距离 ll a[N]; int head[N],tot; struct Edge{ int next; int to; ll dis; }edge[N<<2]; inline void add(int from,int to,ll dis){ edge[++tot].next = head[from]; edge[tot].to = to; edge[tot].dis = dis; head[from] = tot; } vector<int> T;//记录路径 int c[N];//答案数组 int pre[N];//记录前驱 void dfs(int root){ int l = 0,r = T.size() - 1; while(l < r){ int mid = l + r >> 1; if(d[root] - d[T[mid]] <= a[root]) r = mid; else l = mid + 1; } if(T.size() != 0&&d[root] - d[T[r]] <= a[root]){ c[pre[root]] ++; c[pre[T[r]]] --; } T.push_back(root); for(int i = head[root];~i;i = edge[i].next){ int y = edge[i].to; ll dis = edge[i].dis; d[y] = d[root] + dis; dfs(y); } T.pop_back(); } void DFS(int x){ for(int i = head[x];~i;i = edge[i].next){ int y = edge[i].to; DFS(y); c[x] += c[y]; } } int main(){ memset(head,-1,sizeof head); int n; scanf("%d",&n); for(int i = 1;i <= n;++i) scanf("%lld",&a[i]); int u;ll dis; for(int i = 2;i <= n;++i){ scanf("%d%lld",&u,&dis); add(u,i,dis); pre[i] = u; //add(i,u,dis); } dfs(1); DFS(1); for(int i = 1;i <= n;++i) cout<<c[i]<<' '; }
最后
以上就是有魅力百褶裙最近收集整理的关于D. Alyona and a tree（二分 + 树上差分）的全部内容，更多相关D.内容请搜索靠谱客的其他文章。
发表评论 取消回复