http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3602
省赛的C题，方法是hash每个节点定义的状态。
关键貌似要直接DFS递归会爆栈，所以我手写了一个栈模拟。
下面还是贴没有模拟栈之前的代码，提交会sf，不过看起来会好理解很多，模拟部分可以自己去写。
View Code
1
#include<iostream>
2
#include<cstdio>
3
#include<cstdlib>
4
#include<map>
5
#include<cstring>
6
using
namespace
std;
7
typedef
long
long
LL;
8
#define
N 100010
9
struct
node{
10
int
l,r;
11
friend
bool
operator
<(
const
node &x,
const
node &
y){
12
if
(y.l!=x.l)
return
y.l<
x.l;
13
return
y.r<
x.r;
14
}
15
}tree[
2
][N];
16
int
n,m,cs,num[
2
][N];
17
map<node,
int
>
state;
18
int
id(node x){
19
if
(state.find(x)==
state.end())
20
state[x]=++
cs;
21
return
state[x];
22
}
23
int
dfs(
int
u,
int
kind){
24
if
(u==-
1
)
return
0
;
25
node temp;
26
temp.l=
dfs(tree[kind][u].l,kind);
27
temp.r=
dfs(tree[kind][u].r,kind);
28
int
ans=
id(temp);
29
num[kind][ans]++
;
30
return
ans;
31
}
32
int
main(){
33
int
T,a,b;
34
scanf(
"
%d
"
,&
T);
35
while
(T--
){
36
scanf(
"
%d%d
"
,&n,&
m);
37
for
(
int
i=
1
;i<=n;++
i){
38
scanf(
"
%d%d
"
,&a,&
b);
39
tree[
0
][i].l=
a;
40
tree[
0
][i].r=
b;
41
}
42
for
(
int
i=
1
;i<=m;++
i){
43
scanf(
"
%d%d
"
,&a,&
b);
44
tree[
1
][i].l=
a;
45
tree[
1
][i].r=
b;
46
}
47
state.clear();
48
cs=
0
;
49
memset(num,
0
,
sizeof
(num));
50
dfs(
1
,
0
);
51
dfs(
1
,
1
);
52
LL ans=
0
;
53
for
(
int
i=
0
;i<=n+m;++
i)
54
ans+=LL(num[
0
][i])*LL(num[
1
][i]);
55
printf(
"
%lld\n
"
,ans);
56
}
57
return
0
;
58
}
这是模拟栈后的代码，感觉自己写的不好...
View Code
1
#include<iostream>
2
#include<cstdio>
3
#include<cstdlib>
4
#include<map>
5
#include<cstring>
6
using
namespace
std;
7
typedef
long
long
LL;
8
#define
N 100010
9
struct
node{
10
int
l,r;
11
friend
bool
operator
<(
const
node &x,
const
node &
y){
12
if
(y.l!=x.l)
return
y.l<
x.l;
13
return
y.r<
x.r;
14
}
15
}tree[
2
][N];
16
int
n,m,cs,num[
2
][N<<
1
];
17
map<node,
int
>
state;
18
int
id(node x){
19
if
(state.find(x)==
state.end())
20
state[x]=++
cs;
21
return
state[x];
22
}
23
struct
stk{
24
int
u,op,st;
25
}qu[N];
26
void
dfs(
int
u,
int
kind){
27
int
top=
0
;
28
qu[top].u=
u;
29
qu[top++].op=
0
;
30
while
(top){
31
stk now=qu[top-
1
];
32
if
(now.u==-
1
){
33
qu[top-
1
].st=
0
;
34
top--
;
35
}
36
else
if
(!
now.op){
37
qu[top].u=
tree[kind][now.u].l;
38
qu[top].op=
0
;
39
qu[top-
1
].op=
1
;
40
top++
;
41
}
42
else
if
(now.op==
1
){
43
qu[top].u=
tree[kind][now.u].r;
44
qu[top].op=
0
;
45
qu[top-
1
].op=
2
;
46
qu[top-
1
].st=
qu[top].st;
47
top++
;
48
}
49
else
{
50
node temp;
51
temp.l=qu[top-
1
].st;
52
temp.r=
qu[top].st;
53
int
rig=
id(temp);
54
qu[top-
1
].st=
rig;
55
num[kind][rig]++
;
56
top--
;
57
}
58
}
59
}
60
int
main(){
61
int
T,a,b;
62
scanf(
"
%d
"
,&
T);
63
while
(T--
){
64
scanf(
"
%d%d
"
,&n,&
m);
65
for
(
int
i=
1
;i<=n;++
i){
66
scanf(
"
%d%d
"
,&a,&
b);
67
tree[
0
][i].l=
a;
68
tree[
0
][i].r=
b;
69
}
70
for
(
int
i=
1
;i<=m;++
i){
71
scanf(
"
%d%d
"
,&a,&
b);
72
tree[
1
][i].l=
a;
73
tree[
1
][i].r=
b;
74
}
75
state.clear();
76
cs=
0
;
77
memset(num,
0
,
sizeof
(num));
78
dfs(
1
,
0
);
79
dfs(
1
,
1
);
80
LL ans=
0
;
81
for
(
int
i=
0
;i<=cs;++
i)
82
ans+=LL(num[
0
][i])*LL(num[
1
][i]);
83
printf(
"
%lld\n
"
,ans);
84
}
85
return
0
;
86
}
