Tree

题目描述

给出一棵树,问树上距离为k(或小于等于k)的点对是否存在

做了两道很相似的题,就放到一起好了

①询问树上距离为k的点对是否存在。

给定一棵有$n$个点的树以及这棵树上边的距离

有 $m$ 个询问
$n\le 10000,m\le 100,c\le 1000,K\le 10000000$

代码
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
void root(int node, int pre){
siz[node] = 1, more[node] = 0;
//siz[i]: 由i出发遍历到的结点总个数
//more[i]: 以i为rt的所有子树的siz最大值
for(int i = head[node]; i; i = ne[i]){
int To = to[i];
if(v[To] || To == pre) continue;
root(To, node);
siz[node] += siz[To];
more[node] = max(more[node], siz[To]);
}
more[node] = max(more[node], size - siz[node]);
//size:当前所在树的大小
//这里还是很好理解的,就是拿往它父节点方向走子树的大小来更新more数组
if(more[node] < more[rt]) rt = node;
}

set<int>last, s;
//写法有点白痴然后不开O2会T掉
//要改的话是要用那m个询问做背包
//但是懒得改了

void gogo(int node, int pre, int dis){//鬼知道为什么当时要起名叫这个
s.insert(dis);
for(int i = head[node]; i; i = ne[i]){
int To = to[i];
if(v[To] || To == pre) continue;
gogo(To, node, dis + val[i]);
}
}

void cal(int node){
for(int i = head[node]; i; i = ne[i]){
int To = to[i];
if(v[To]) continue;
gogo(To, node, val[i]);
for(set<int>::iterator it = s.begin(); it != s.end(); ++ it){
for(set<int>::iterator _it = last.begin(); _it != last.end(); ++ _it){
can[*it + (*_it)] = 1;
}
}
for(set<int>::iterator it = s.begin(); it != s.end(); ++ it){
last.insert(*it);
s.erase(*it);
}
}
for(set<int>::iterator it = last.begin(); it != last.end(); ++ it) can[*it] = 1;
last.clear();
}

void check(int node){
v[node] = 1;//这里!统计完的节点要做标记,不能够再被经过了
cal(node);//统计经过node的路径的答案
for(int i = head[node]; i; i = ne[i]){
int To = to[i];
if(v[To]) continue;
size = siz[To], more[rt] = MAXN;//每一次root前都要初始化啊
root(To, node);//每一次check前都要root啊
check(rt);
}
}

int main(){
n = read(), m = read();
for(int i = 1, a, b, c; i < n; ++ i){
a = read(), b = read(), c = read();
add(a, b, c), add(b, a, c);
}
for(int i = 1; i <= m; ++ i) k[i] = read();
more[rt] = MAXN, size = n;//每一次root前都要初始化啊
root(1, 0);//每一次check前都要root啊
check(rt);
for(int i = 1; i <= m; ++ i){
can[k[i]] ? printf("AYE\n") : printf("NAY\n");
}
return 0;
}
②询问有多少点对满足两者间的距离小于等于k

给定一棵有$n$个点的树以及这棵树上边的距离

$n \le 40000$

代码
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
//作死拿树状数组套进去做了
//然后果然TLE了啊...
//所以说不会算时间复杂度就给我谨慎一点啊白痴

//其他的代码都没有变化
//除了把set改成手动模拟的栈以外..
//但是每次都要sort一遍?
//那么复杂度究竟哪个更优一点呢?
int cal(int node, int dis){
s[0] = 0;
gogo(node, 0, dis);//这份代码的gogo是会一次性统计完从node出发的所有路径的dis的
sort(s + 1, s + s[0] + 1);//迷之复杂度?
int cou = 0, r = s[0];
for(int l = 1; l <= s[0]; ++ l){
while(s[l] + s[r] > m) -- r;
if(r <= l) break;
cou += r - l;
}
//显而易见的匹配啊
//s[1]是0所以不会漏掉以node为顶点的情况
return cou;
}

void check(int node){
v[node] = 1;
ans += cal(node, 0);//先全部加上来
for(int i = head[node]; i; i = ne[i]){
int To = to[i];
if(v[To]) continue;
ans -= cal(To, val[i]);
//减掉在同一个子树里跑了重复边的情况
//初始dis是val[i]不是0!!!!!
//记住了啊
size = siz[To], more[rt = 0] = MAXN;
root(To, node);
check(rt);
}
}

int main(){
while(1){
n = read(), m = read();
if(!n && !m) return 0;
cnt = rt = ans = 0;
for(int i = 1, a, b, c; i < n; ++ i){
a = read(), b = read(), c = read();
add(a, b, c), add(b, a, c);
}
more[rt] = MAXN, size = n;
root(1, 0);
check(rt);
printf("%d\n", ans);
for(int i = 1; i <= n; ++ i) head[i] = 0, v[i] = 0;
//我gc从来就没有相信过memset的复杂度!
}
}