正解还不会
用暴力搜索弄到了90.。。
bfs与dfs都能过90
思路：
先弄一个f数组
记得是这个点的最短路，就是破败指针
在爆搜剪枝
bfs1
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<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int tot,head[1999999],nex[1999999],to[1999999],f[209999],s[209999];
int n,m;
int add(int x,int y){
++tot;
nex[tot]=head[x];
to[tot]=y;
head[x]=tot;
}
void bfs(int x){
queue<int> q;
q.push(x);
f[x]=0;
while(!q.empty()){
int o=q.front();q.pop();
for(int i=head[o];i;i=nex[i])
{
int tmp=to[i];
if(f[tmp]>f[o]+1)
{
f[tmp]=f[o]+1;
q.push(tmp);
}
}
}
}
int main() {
freopen("cicada.in","r",stdin);
freopen("cicada.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n-1;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
memset(f,127,sizeof(f));
bfs(1);
for(int i=1;i<=m;i++)
{
int a,x;
scanf("%d%d",&a,&x);
if(a==1)
{
bfs(x);
}
else{
printf("%d" "\n",f[x]);
}
}
return 0;
}
dfs1
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#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define D "%d"
#define prf printf
#define scf scanf
int ans,cnt,f[999999];
int head[999999],nex[999999],to[999999];
int add(int x,int y){
cnt++;
nex[cnt]=head[x];
to[cnt]=y;
head[x]=cnt;
}
void dfs(int fa,int x,int tot){
f[x]=min(f[x],tot);
for(int i=head[x];i;i=nex[i])
{
int tmp=to[i];
if(tmp!=fa&&f[tmp]>tot)
dfs(x,tmp,tot+1);
}
}
int n,m;
int main(){
freopen("cicada.in","r",stdin);
freopen("cicada.out","w",stdout);
scf(D D,&n,&m);
n--;
memset(f,127,sizeof(f));
while(n--)
{
int x,y;
scf(D D,&x,&y);
add(x,y);
add(y,x);
}
dfs(1,1,0);
while(m--)
{
int a,x;
scf(D D,&a,&x);
if(a==1&&f[x])
dfs(x,x,0);
else prf(D "\n",f[x]);
}
}