luogu4006|loj2324|清华集训 2017|小Y和二叉树

给定点的连边情况,求字典序最小的中序遍历

  • Sample

    • Input

      1
      2
      3
      4
      5
      4
      3 2 3 4
      1 1
      1 1
      1 1
    • Output

      1
      2 1 3 4

loj做吧,可以下数据。

显然我们从$min_{k_i\le2}i$开始考虑。

显然A就是序列的第一个数,也就是说上面式子里的$i$,$k_i$不能$>2$是因为那样$A$就有右子树,也就不是序列的第一个数了,然后$i$要尽量小。

我们要分情况讨论,先设$f_i$表示以$A$为根中序遍历可能的最小值。

那么$f_i=min\cases{\cases{i&$k_i\le2$\\0&$k_i=3$}\\f_u&$uv$有边连接}$

然后贪心遍历。

现在遍历顺序是:A-B-f-G-C-D-E

先把A小的子树放在B

如果没有两个儿子,那么当且仅当$f_{son}=son$时放C,其它放B

注意细节。

代码:

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#define N 1000010
#define inf (1<<30)
int n,d[N],s[N],v[N<<1],p[N],k,f[N];
void dfs(int x)
{
p[x]=1;
f[x]=d[x]==3?inf:x;
fr(i,1,d[x])
if(!p[v[s[x-1]+i]])
{
dfs(v[s[x-1]+i]);
f[x]=min(f[x],f[v[s[x-1]+i]]);
}
}
void print1(int x)
{
p[x]=0;
if(d[x]==1)
{
printf(" %d",x);
return;
}
if(d[x]==2)
{
int son;
fr(i,1,2)
if(p[v[s[x-1]+i]])
son=v[s[x-1]+i];
if(f[son]<x)
{
print1(son);
printf(" %d",x);
}
else
{
printf(" %d",x);
print1(son);
}
}
if(d[x]==3)
{
int son1=0,son2=0;
fr(i,1,3)
if(p[v[s[x-1]+i]])
{
son1=son2;
son2=v[s[x-1]+i];
}
if(f[son1]>f[son2])
{
int _=son1;
son1=son2;
son2=_;
}
print1(son1);
printf(" %d",x);
print1(son2);
}
}
void print2(int x)
{
p[x]=0;
if(d[x]==1)
{
printf(" %d",x);
return;
}
if(d[x]==2)
{
int son;
fr(i,1,2)
if(p[v[s[x-1]+i]])
son=v[s[x-1]+i];
printf(" %d",x);
if(son>f[son])
print1(son);
else
print2(son);
}
if(d[x]==3)
{
int son1=0,son2=0;
fr(i,1,3)
if(p[v[s[x-1]+i]])
{
son1=son2;
son2=v[s[x-1]+i];
}
if(f[son1]>f[son2])
{
int _=son1;
son1=son2;
son2=_;
}
printf(" %d",x);
print1(son1);
print2(son2);
}
}
int main()
{
n=read();
fr(i,1,n)
{
d[i]=read();
s[i]=s[i-1]+d[i];
fr(j,1,d[i])
v[s[i-1]+j]=read();
sort(v+s[i-1]+1,v+s[i]+1);
}
fd(i,n,1)
if(d[i]<=2)
k=i;
p[k]=1;
fr(i,1,d[k])
dfs(v[s[k-1]+i]);
printf("%d",k);
if(d[k]==2&&f[v[s[k]]]<f[v[s[k]-1]])
{
int _=v[s[k]];
v[s[k]]=v[s[k]-1];
v[s[k]-1]=_;
}
if(d[k]==1)
if(v[s[k]]>f[v[s[k]]])
print1(v[s[k]]);
else
print2(v[s[k]]);
else
{
print1(v[s[k]-1]);
print2(v[s[k]]);
}
putchar(10);
return 0;
}