codeforces-740D-Alyona and a tree-树上二分

题目链接

今天ccpc决赛，高老师队三题垫底有点惨……伟佳巨队五题拿铜，orz……
昨天跟着几位大佬把新生校赛的pc2和题目数据搞了搞，还没搞完……感觉下周校赛药丸……下下周上海EC-final，有点虚……wzm和fdf被线代考试封印了，lpf和kn准备缓考跟我去EC……感觉他们两个都是喜欢推公式搞数学的人（orz，我最不喜欢干的事情）,这两周就稍微多搞点数据结构吧，正好这两次cf的D都是树，树上的东西感觉都不太会……这个临时队伍也不指望能拿牌了吧，去上海就当旅游，虽然就在家边上……

题意：给你一棵树，每个节点和边有权值。两个点u,v的距离定义为u到v的简单路径上所有边的权值和。如果u在v的子树中，并且u,v的距离小于等于点u的权值，那么称v控制了u。让你输出每个点能控制的点的个数。

思路：一开始就想到了二分，但是一直不会搞怎么维护所有已经进栈的点到当前点的距离……也是sb了，一神跟我说了半天还是一头雾水……给我看代码才明白他讲的重点和我不明白的不是一个东西……用前缀和记录每个点到根节点的距离，二分的时候减一下就行了……真的好sb……回溯的时候再记录答案。
看到赵姐姐在这个题上用的树状数组来更新答案，感觉那样好难想，而且很麻烦……一神提供的方法是，对于二分搜到的那个点以上的点，直接在回溯的时候少加上当前点，这样又好写，理解起来又简单。

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
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;
struct node
{
	int v;
	long long val;
};
vector<node >g[200005];
long long a[200005];
long long ans[200005];
long long dis[200005];  //从根到当前点的距离
int sta[200005]; //栈 
int cnt;
void dfs(int u,long long deep)
{
	sta[++cnt]=u;
	dis[u]=deep;
	int size=g[u].size();
	for(int i=0;i<size;i++)
	{
		ans[u]++;
		dfs(g[u][i].v,deep+g[u][i].val);
		ans[u]+=ans[g[u][i].v];
	}
	
	int l=0,r=cnt-1;
	while(l<r)      // 找出深度最大的不能控制u的点 
	{
		int mid=(l+r+1)/2;
		if(dis[u]-dis[sta[mid]]>a[u])l=mid;
		  else r=mid-1; 
	}
	//printf("u:%d v:%d\n",u,sta[l]);
	ans[sta[l]]--;
	cnt--;
}
int  main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%I64d",&a[i]);
	for(int i=2;i<=n;i++)
	{
		long long v,val;
		scanf("%I64d%I64d",&v,&val);
		g[v].push_back((node){i,val});
	}
    dfs(1,0);
    for(int i=1;i<=n;i++)printf("%I64d ",ans[i]);
    return 0;
}