迟到了半小时开打，不然rank还可以更好看点……
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
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
|
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException{
StreamTokenizer in=new StreamTokenizer(new BufferedInputStream(System.in));
PrintWriter out=new PrintWriter(System.out);
while(in.nextToken()!=StreamTokenizer.TT_EOF){
int n=(int)in.nval;
in.nextToken();
int m=(int)in.nval;
boolean has=false;
for(int i=1;i<=m;i++){
in.nextToken();
int u=(int)in.nval;
in.nextToken();
int v=(int)in.nval;
if (u==1&&v==n||u==n&&v==1)
has=true;
}
if (has)
out.println(1+" "+n*(n-1)/2);
else
out.println(1+" "+1);
}
out.flush();
out.close();
}
}
|
如果点1与点n直接相连，那么就是距离最短了。
要同时满足不同与相似，就是要求结点数相等，各结点到树根1的距离分别相等（即深度分别相同），且存在父节点不同的结点。
可以说就是判断同一深度上的结点互换后是否能得到新的结构。
若有某一深度上的结点数多于一个，那么大概可以通过同层互换获得新的结构。
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
87
88
89
90
|
import java.io.*;
import java.util.*;
public class Main {
final static int maxn=2010;
static Graph G=new Graph(maxn);
static int[] dep;
static HashSet<Integer> st=new HashSet<Integer>();
static void bfs(int st){
Queue<Integer> que=new LinkedList<Integer>();
que.add(st);
while(!que.isEmpty()){
int u=que.poll();
for(int i=G.h[u];i>-1;i=G.edge[i].next){
int v=G.edge[i].to;
if (dep[v]>0) continue;
dep[v]=dep[u]+1;
que.add(v);
}
}
}
public static void main(String[] args) throws IOException{
StreamTokenizer in=new StreamTokenizer(new BufferedInputStream(System.in));
PrintWriter out=new PrintWriter(System.out);
while(in.nextToken()!=StreamTokenizer.TT_EOF){
int n=(int)in.nval;
G.clear();
dep=new int[n+1];
dep[1]=1;
for(int i=1;i<n;i++){
in.nextToken();
int u=(int)in.nval;
in.nextToken();
int v=(int)in.nval;
G.add(u, v);
G.add(v, u);
}
bfs(1);
boolean ans=true;
st.clear();
for(int i=1;i<=n;i++)
if (st.contains(dep[i])){
ans=false;
break;
}
else
st.add(dep[i]);
out.println(ans?"YES":"NO");
}
out.flush();
out.close();
}
}
class Edge{
int to,next;
Edge(int _u,int _v){
to=_u;next=_v;
}
}
class Graph{
int[] h;
int sz;
Edge[] edge;
Graph(int size){
sz=size;
h=new int[sz+1];
edge=new Edge[sz+1];
Arrays.fill(h, -1);
h[0]=0;
}
void clear(){
h=new int[sz+1];
edge=new Edge[sz+1];
Arrays.fill(h, -1);
h[0]=0;
}
void add(int u,int v){
edge[h[0]]=new Edge(v,h[u]);
h[u]=h[0]++;
}
}
|
然而错了。
适当地列举一些情况，发现若树的深度仅有2，那么它始终是特殊的。
可是加上这一判断仍不够。
进一步的举例发现，若树上非最底层有某一层结点多于一个，就能变换形成新结构
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
87
88
89
90
91
92
93
94
95
96
97
|
import java.io.*;
import java.util.*;
public class Main {
final static int maxn=2010;
static Graph G=new Graph(maxn);
static int[] dep;
static HashSet<Integer> st=new HashSet<Integer>();
static void bfs(int st){
Queue<Integer> que=new LinkedList<Integer>();
que.add(st);
while(!que.isEmpty()){
int u=que.poll();
for(int i=G.h[u];i>-1;i=G.edge[i].next){
int v=G.edge[i].to;
if (dep[v]>0) continue;
dep[v]=dep[u]+1;
que.add(v);
}
}
}
public static void main(String[] args) throws IOException{
StreamTokenizer in=new StreamTokenizer(new BufferedInputStream(System.in));
PrintWriter out=new PrintWriter(System.out);
while(in.nextToken()!=StreamTokenizer.TT_EOF){
int n=(int)in.nval;
G.clear();
dep=new int[n+1];
dep[1]=1;
for(int i=1;i<n;i++){
in.nextToken();
int u=(int)in.nval;
in.nextToken();
int v=(int)in.nval;
G.add(u, v);
G.add(v, u);
}
bfs(1);
boolean ans=true;
st.clear();
int maxd=0;
for(int i=1;i<=n;i++)
maxd=Math.max(dep[i], maxd);
for(int i=1;i<=n;i++)
if (st.contains(dep[i])){
if (dep[i]<maxd){
ans=false;
break;
}
}
else
st.add(dep[i]);
if (maxd<3)
ans=true;
out.println(ans?"YES":"NO");
}
out.flush();
out.close();
}
}
class Edge{
int to,next;
Edge(int _u,int _v){
to=_u;next=_v;
}
}
class Graph{
int[] h;
int sz;
Edge[] edge;
Graph(int size){
sz=size;
h=new int[sz+1];
edge=new Edge[sz+1];
Arrays.fill(h, -1);
h[0]=0;
}
void clear(){
h=new int[sz+1];
edge=new Edge[sz+1];
Arrays.fill(h, -1);
h[0]=0;
}
void add(int u,int v){
edge[h[0]]=new Edge(v,h[u]);
h[u]=h[0]++;
}
}
|
这与题解中所说的“一棵树是独特的当且仅当任意处于每一个深度的点数是1 1 1 1 … 1 1 x”相符（我个人将这种形态称作“呈扫帚状”）