codeforces Xenia and Tree

本文从WordPress迁移而来, 查看全部WordPress迁移文章

树dp

昨天cf的E题,给一颗无根树,一开始只有1为红色,其余点为蓝色。

1 x : 将x点设为红色

2 x : 询问距离x点最近的红点的距离(是距离不是标号,如果自身是红点,距离为0)

这题做法各异,这种是比较水的

这种问题,有一个特点就是,难度在查询,另外如果树中的红点多了,那么查询的时间会更短,因为使用的是BFS搜索。对于每次修改操作,我们除了修改,还进行一次类似于松弛的操作,就是以修改的这个点为中心,bfs向四周松弛,这里需要记录一个信息,d[u],表示离u最近的红点的距离,这里,不同的d[u],对应的红点不同。

当在一个限制值内的时候,每次修改,都去做一次松弛,而查询的时候,可以做到O(1),直接读取d[x]。但超过了限制值,也就是说树中的红点很多了,那么,其实直接以查询点x开始做bfs,直接找到第一个红点,会更快。
松弛写为bfs,从查询点开始搜索写为search

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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 100010
#define INF 0x3f3f3f3f
#define LIM 500
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,tot,head[N];
struct edge{
int u,v,next;
}e[2*N];
int d[N],dis[N];
int que[N],front,rear;
bool color[N];
int vis[N];

inline void add(int u,int v){
e[tot].u = u; e[tot].v = v;
e[tot].next = head[u]; head[u] = tot++;
}

void bfs(int s){
front = rear = 0;
d[s] = 0; que[rear++] = s;
while(front < rear){
int u = que[front++];
for(int k = head[u]; k != -1 ; k = e[k].next){
int v = e[k].v;
if(d[u] + 1 < d[v]){
d[v] = d[u] + 1;
que[rear++] = v;
}
}
}
}

int search(int s,int id){
if(color[s]) return 0;
front = rear = 0;
dis[s] = 0; que[rear++] = s; vis[s] = id;
while(front < rear){
int u = que[front++];
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v;
if(vis[v] == id) continue;
vis[v] = id;
dis[v] = dis[u] + 1;
if(color[v]) return dis[v];
que[rear++] = v;
}
}
}

int main(){
int m;
while(scanf("%d%d",&n,&m)!=EOF){
tot = 0; cl(head,-1);
for(int i = 1; i < n; i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v); add(v,u);
}
cl(color,false);
color[1] = true;
cl(d,0x3f);
cl(vis,-1);
bfs(1);
int cnt = 1;
while(m--){
int op,x;
scanf("%d%d",&op,&x);
if(op == 1){
cnt++;
color[x] = true;
if(cnt <= LIM) bfs(x);
}
else{
if(cnt <= LIM) printf("%d\n",d[x]);
else printf("%d\n",search(x,m));
}
}
}
return 0;
}