atcoder regular 175 题解 A-C D还未解决

人生乱弹 2年前 (2024) admin

6 0 0

A
要么所有人全部做左边的筷子，要么全部右边的筷子。依次处理。
大家按照顺序拿筷子，如果成立，当前的人，所需方向的筷子肯定没拿。如果所需方向的反方向的筷子被拿了，就结果*2（第一选择方向可以任选）；反而，肯定要求第一选择方向是所需方向，就结果*1。

B
左括号，右括号数目= x，y
1. abs(x-y)/2，肯定就是修改的(->) 、 )->( 的数目。如果是)->(，一开始把“最左边”的这些')'改成’('。
2. (->) 、 )->( 花费为B，也可以花费为2*A的方式解决
3. 从左到右，记录 '(' - ')' 的数目，找出有')‘，使得 '(' - ')' = -1的情况，这时候需要B/2A了。')‘->'('后，'(' - ')'变为1。记录最少需要B/2A的次数。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cstdbool>
#include <string>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <ctime>
#include <stack>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define ll long long
#define ull unsigned long long

const ll mod_1=1e9+7;
const ll mod_2=998244353;

const double eps_1=1e-5;
const double eps_2=1e-10;

const int maxn=1e6+10;

char str[maxn];

int main()
{
int n,len,i;
ll cha=0,jia_cnt=0,cnt_lower_zero=0,a,b;
//ll result=0;
scanf("%d%lld%lld",&n,&a,&b);
scanf("%s",str);
len=strlen(str);

for (i=0;i<len;i++)
if (str[i]=='(')
cha++;
else
cha--;
if (cha<0)
jia_cnt=abs(cha);
cha=abs(cha)/2;

for (i=0;i<len;i++)
{
if (str[i]==')')
jia_cnt--;
else
jia_cnt++;
if (jia_cnt<0)
{
jia_cnt=1;
cnt_lower_zero++;
}
}
if (a>b*2)
printf("%lld",(cha+cnt_lower_zero*2) *b );
else
printf("%lld",cha*b + cnt_lower_zero*a );

return 0;
}
/*
(((((((((
)))))

3 2 2
((((((

3 10 2
((((((

3 2 10
((((((

3 2 2
))))))

3 2 10
))))))

3 2 10
)))(((

3 10 2
)))(((

3 2 2
)))(((
*/

C
遇到这种题很头疼，很容易找不到错误的地方，制造不出可以找到错误的样例。
这种题目应该先多制造几个样例，然后把一些条理理清楚了再写会比较好

官方题解看着有点晕，也看到写得特别短的代码，有点不理解……

我的是，把这些分为[l1,r1] [l2,r2] [l3,r3] ... [lk,rk]的区间，它们互不交集。然后区间有升有降。
如果l_{i-1} -> l_{i} -> l_{i+1} 是降、升的趋势，那么这个区间的数值应该选择r_{i}，还有最左边和最右边的区间要做特殊处理，其它都选择l_{i}。
对于一个区间，它相对于上个区间是升的话，然后这个区间最左边的几个数值可以往上个区间那个靠，这是为了让字典序最小，只要满足条件即可。
同理，对于一个区间，它相对于下个区间是降的话，然后这个区间最右边的几个数值可以往下个区间那个靠，这是为了让字典序最小，只要满足条件即可。

1 /*
2 1 制造比较小的随机数据
3 10以内的
4 2 然后用std程序跑结果
5 */
6
7 #include <cstdio>
8 #include <cstdlib>
9 #include <cstring>
10 #include <cmath>
11 #include <cstdbool>
12 #include <string>
13 #include <algorithm>
14 #include <iostream>
15 #include <sstream>
16 #include <ctime>
17 #include <stack>
18 #include <vector>
19 #include <queue>
20 #include <set>
21 #include <map>
22 using namespace std;
23
24 const double eps_1=1e-5;
25 const double eps_2=1e-10;
26
27 const int maxn=5e5+10;
28
29
30
31
32 int l[maxn],r[maxn],v[maxn],result[maxn];
33 int ql[maxn],qr[maxn],range[maxn];
34
35 int main()
36 {
37 int inf=1e9+10;
38 int n,i,j,k,o,ll=-inf,rr=inf,cnt=1,temp;
39 range[0]=0;
40 scanf("%d",&n);
41 for (i=1;i<=n;i++)
42 {
43 scanf("%d%d",&l[i],&r[i]);
44
45 if (r[i]<ll || l[i]>rr)
46 {
47 range[cnt]=i-1;
48 ql[cnt]=ll;
49 qr[cnt]=rr;
50
51 ll=l[i];
52 rr=r[i];
53 cnt++;
54 }
55
56 ll=max(ll, l[i]);
57 rr=min(rr, r[i]);
58 }
59
60 ql[cnt]=ll;
61 qr[cnt]=rr;
62 range[cnt]=n;
63
64
65
66
67 for (i=1;i<=cnt;i++)
68 v[i]=ql[i];
69
70 if (cnt!=1)
71 {
72
73 i=1;
74 while (i<cnt)
75 {
76 if (i<cnt && ql[i]>ql[i+1])
77 {
78 while (ql[i]>ql[i+1])
79 i++;
80 if (i!=cnt)
81 v[i]=qr[i];
82 }
83 i++;
84 }
85
86 if (ql[1]<ql[2])
87 v[1]=qr[1];
88
89 if (ql[cnt-1]>ql[cnt])
90 v[cnt]=qr[cnt];
91 }
92
93
94 for (i=1 ;i<=cnt;i++)
95 {
96 if (i!=1 && v[i]>v[i-1])
97 {
98 temp = l[ range[i-1]+1 ];
99 for (o=range[i-1]+1 ; o<=range[i] ; o++)
100 {
101 if (l[o]>temp)
102 temp=l[o];
103 if (temp==v[i])
104 break;
105 result[o]=temp;
106 }
107 }
108 else
109 o=range[i-1]+1;
110
111 if (i!=cnt && v[i]>v[i+1])
112 {
113 temp = v[i+1];
114 for (k=range[i] ; k>=o ; k--)
115 {
116 if (l[k]>temp)
117 temp=l[k];
118 if (temp==v[i])
119 break;
120 result[k]=temp;
121 }
122 }
123 else
124 k=range[i];
125
126 for (j=o ; j<=k ; j++)
127 result[j]=v[i];
128
129 }
130
131 for (i=1;i<=n;i++)
132 {
133 printf("%d",result[i]);
134 if (i!=n)
135 printf(" ");
136 }
137
138 return 0;
139 }
140 /*
141 15
142 5 29
143 9 28
144 15 19
145 4 26
146 7 23
147 10 13
148 12 25
149 3 11
150 6 17
151 1 21
152 24 27
153 2 8
154 14 18
155 20 22
156 16 30
157
158
159
160 15 15 15 12 12 12 12 11 11 11 24 8 14 20 20
161
162
163
164
165
166 5
167 50 60
168 40 50
169 30 40
170 20 30
171 10 20
172
173 5
174 10 20
175 20 30
176 30 40
177 40 50
178 50 60
179
180 2
181 10 30
182 40 60
183
184 2
185 40 60
186 10 30
187
188 5
189 100 200
190 300 400
191 500 600
192 50 70
193 20 40
194
195 */

1 /*
2 1 制造比较小的随机数据
3 10以内的
4 2 然后用std程序跑结果
5 */
6
7 #include <cstdio>
8 #include <cstdlib>
9 #include <cstring>
10 #include <cmath>
11 #include <cstdbool>
12 #include <string>
13 #include <algorithm>
14 #include <iostream>
15 #include <sstream>
16 #include <ctime>
17 #include <stack>
18 #include <vector>
19 #include <queue>
20 #include <set>
21 #include <map>
22 using namespace std;
23
24 const double eps_1=1e-5;
25 const double eps_2=1e-10;
26
27 const int maxn=5e5+10;
28
29
30 int l[maxn],r[maxn],v[maxn],result[maxn];
31 int ql[maxn],qr[maxn],range[maxn];
32
33 int main()
34 {
35 int inf=1e9+10;
36 int n,i,j,ll=-inf,rr=inf,cnt=0,temp;
37 range[0]=0;
38 scanf("%d",&n);
39 for (i=1;i<=n;i++)
40 {
41 scanf("%d%d",&l[i],&r[i]);
42
43 if (r[i]<ll || l[i]>rr)
44 {
45 ++cnt;
46 range[cnt]=i-1;
47 ql[cnt]=ll;
48 qr[cnt]=rr;
49
50 ll=-inf,rr=inf;
51 }
52
53 ll=max(ll, l[i]);
54 rr=min(rr, r[i]);
55 }
56
57 ++cnt;
58 range[cnt]=n;
59 ql[cnt]=ll;
60 qr[cnt]=rr;
61
62
63 for (i=1;i<=cnt;i++)
64 if (cnt!=1 && ((i==1 || ql[i]<ql[i-1]) && (i==cnt || ql[i]<ql[i+1])))
65 v[i]=qr[i];
66 else
67 v[i]=ql[i];
68 j=1;
69 for (i=1;i<=n;i++)
70 {
71 result[i]=v[j];
72 if (j!=cnt && i==range[j])
73 j++;
74 }
75
76 for (i=1;i<=cnt;i++)
77 {
78 //asc
79 if (i!=1 && v[i]>v[i-1])
80 {
81 j=range[i-1]+1;
82 temp = v[i-1];
83 while (temp<ql[i])
84 {
85 temp=max(temp,l[j]);
86 result[j]=temp;
87 j++;
88 }
89 }
90
91 //des
92 if (i!=cnt && v[i]>v[i+1])
93 {
94 j=range[i];
95 temp=v[i+1];
96 while (temp<ql[i])
97 {
98 temp=max(temp,l[j]);
99 result[j]=temp;
100 j--;
101 }
102 }
103 }
104
105 for (i=1;i<=n;i++)
106 {
107 printf("%d",result[i]);
108 if (i!=n)
109 printf(" ");
110 }
111
112 return 0;
113 }
114 /*
115 15
116 5 29
117 9 28
118 15 19
119 4 26
120 7 23
121 10 13
122 12 25
123 3 11
124 6 17
125 1 21
126 24 27
127 2 8
128 14 18
129 20 22
130 16 30
131
132
133
134 15 15 15 12 12 12 12 11 11 11 24 8 14 20 20
135
136
137
138
139
140 5
141 50 60
142 40 50
143 30 40
144 20 30
145 10 20
146
147 5
148 10 20
149 20 30
150 30 40
151 40 50
152 50 60
153
154 2
155 10 30
156 40 60
157
158 2
159 40 60
160 10 30
161
162 5
163 100 200
164 300 400
165 500 600
166 50 70
167 20 40
168
169 */

把样例里的数值离散化，方便看得清

创建小的数据

1 /*
2 10以内数据
3 */
4 #include <cstdio>
5 #include <cstdlib>
6 #include <cstring>
7 #include <cmath>
8 #include <cstdbool>
9 #include <string>
10 #include <algorithm>
11 #include <iostream>
12 #include <sstream>
13 #include <ctime>
14 #include <stack>
15 #include <vector>
16 #include <queue>
17 #include <set>
18 #include <map>
19 using namespace std;
20 #define ll long long
21 #define ull unsigned long long
22
23 const ll mod_1=1e9+7;
24 const ll mod_2=998244353;
25
26 const double eps_1=1e-5;
27 const double eps_2=1e-10;
28
29 const int maxn=2e5+10;
30
31
32
33
34
35
36 int main()
37 {
38 int n=30,range=30,i,x,y;
39 srand((int)time(0));
40 printf("%d\n",n);
41
42 for (i=1;i<=n;i++)
43 {
44 x=rand()%range;
45 y=rand()%range;
46 if (x>y)
47 swap(x,y);
48 printf("%d %d\n",x,y);
49 }
50
51
52 return 0;
53 }

暴力用程序获取小数据的输出结果
比如数据l_i,r_i在1-x范围内
然后结果可以是(r_i - l_i + 1) ^n种，然后在最小化的情况下，最小序列的输出
复杂度(r_i - l_i + 1) ^n
9个l_i-r_i范围为1-10的数据
12个l_i-r_i范围为1-5的数据
17个l_i-r_i范围为1-3的数据
看着也勉强还行
如果真要到这种地步的话

如果是赛后，对着test case或者是用别人的std代码跑一些样例出来

D
往子树都整体，DP这些角度想
用的是官方题解的方法
对于K，最小的是N
然后要想办法，增加K的数值
设置这个点都小于/大于它的子树里面的点，K分别增加子树点数目-1，0。
然后设置哪个点的数值为多少。dfs处理

这样写有问题，看某个下面的样例

1 #include <cstdio>
2 #include <cstdlib>
3 #include <cstring>
4 #include <cmath>
5 #include <cstdbool>
6 #include <string>
7 #include <algorithm>
8 #include <iostream>
9 #include <sstream>
10 #include <ctime>
11 #include <stack>
12 #include <vector>
13 #include <queue>
14 #include <set>
15 #include <map>
16 using namespace std;
17 #define LL long long
18 #define ULL unsigned long long
19
20 const LL mod_1=1e9+7;
21 const LL mod_2=998244353;
22
23 const double eps_1=1e-5;
24 const double eps_2=1e-10;
25
26 const int maxn=2e5+10;
27
28 LL value;
29
30 vector<int> adj[maxn], child[maxn];
31 bool hap[maxn];
32 int subtree[maxn], use[maxn], ind[maxn];
33
34 pair<int,int> v[maxn];
35
36 void find_child(int d)
37 {
38 subtree[d]=1;
39
40 hap[d]=1;
41 for (auto chi:adj[d])
42 if (!hap[chi])
43 {
44 child[d].push_back(chi);
45 find_child(chi);
46 subtree[d] += subtree[chi];
47 }
48 }
49
50 void dfs(int d, int l, int r)
51 {
52 int ind_begin;
53 if (use[d]==1)
54 ind[d]=l, ind_begin=l+1;
55 else
56 ind[d]=r, ind_begin=l;
57
58 for (auto chi:child[d])
59 {
60 dfs(chi,ind_begin, ind_begin+subtree[chi]-1);
61 ind_begin+=subtree[chi];
62 }
63
64 }
65
66 int main()
67 {
68 int n,i,x,y;
69 LL max_value=0;
70 memset(hap,0,sizeof(hap));
71 cin>>n>>value;
72 for (i=1;i<n;i++)
73 {
74 cin>>x>>y;
75 adj[x].push_back(y);
76 adj[y].push_back(x);
77 }
78
79 find_child(1);
80
81 for (i=1;i<=n;i++)
82 max_value += subtree[i];
83
84 if (value<n || n>max_value)
85 {
86 cout<<"No";
87 return 0;
88 }
89
90 for (i=1;i<=n;i++)
91 v[i] = {subtree[i]-1, i};
92 sort(v+1, v+n+1);
93 value-=n;
94
95 for (i=n;i>=1;i--)
96 if (value>=v[i].first)
97 {
98 use[ v[i].second ]=1;
99 value-=v[i].first;
100 }
101 else
102 use[ v[i].second ]=-1;
103
104
105 dfs(1,1,n);
106
107 cout<<"Yes"<<endl;
108 for (i=1;i<=n;i++)
109 {
110 cout<<ind[i];
111 if (i==n)
112 cout<<endl;
113 else
114 cout<<" ";
115 }
116
117 return 0;
118 }
119 /*
120 5 4
121 1 2
122 2 3
123 3 4
124 4 5
125
126 ===
127
128 5 5
129 1 2
130 2 3
131 3 4
132 4 5
133
134 ===
135
136 5 6
137 1 2
138 2 3
139 3 4
140 4 5
141
142 ===
143
144 5 7
145 1 2
146 2 3
147 3 4
148 4 5
149
150 ===
151
152 5 15
153 1 2
154 2 3
155 3 4
156 4 5
157
158 ===
159
160 5 16
161 1 2
162 2 3
163 3 4
164 4 5
165
166 ===
167
168 5 5
169 1 2
170 1 3
171 1 4
172 1 5
173
174 ===
175
176 有问题
177 5 6
178 1 2
179 1 3
180 1 4
181 1 5
182
183 ===
184
185 5 9
186 1 2
187 1 3
188 1 4
189 1 5
190 */

看到某位大佬的代码很简洁

1 //#pragma GCC optimize("Ofast")
2 //#pragma GCC target("avx,avx2,fma")
3 //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")
4 #include <iostream>
5 #include <cstdio>
6 #include <cstdlib>
7 #include <algorithm>
8 #include <cmath>
9 #include <vector>
10 #include <set>
11 #include <map>
12 #include <unordered_set>
13 #include <unordered_map>
14 #include <queue>
15 #include <ctime>
16 #include <cassert>
17 #include <complex>
18 #include <string>
19 #include <cstring>
20 #include <chrono>
21 #include <random>
22 #include <bitset>
23 #include <array>
24 #include <climits>
25 using namespace std;
26
27 #ifdef LOCAL
28 #define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
29 #else
30 #define eprintf(...) 42
31 #endif
32
33 using ll = long long;
34 using ld = long double;
35 using uint = unsigned int;
36 using ull = unsigned long long;
37 using pii = pair<int, int>;
38 using pli = pair<ll, int>;
39 using pll = pair<ll, ll>;
40 mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
41 ll myRand(ll B) {
42 return (ull)rng() % B;
43 }
44
45 #define mp make_pair
46 #define all(x) (x).begin(),(x).end()
47
48 clock_t startTime;
49 double getCurrentTime() {
50 return (double)(clock() - startTime) / CLOCKS_PER_SEC;
51 }
52
53 ll floor_div(ll x, ll y) {
54 assert(y != 0);
55 if (y < 0) {
56 y = -y;
57 x = -x;
58 }
59 if (x >= 0) return x / y;
60 return (x + 1) / y - 1;
61 }
62 ll ceil_div(ll x, ll y) {
63 assert(y != 0);
64 if (y < 0) {
65 y = -y;
66 x = -x;
67 }
68 if (x <= 0) return x / y;
69 return (x - 1) / y + 1;
70 }
71 template<typename T>
72 T sqr(T x) {
73 return x * x;
74 }
75
76 const int N = 200200;
77 vector<int> g[N];
78 int h[N];
79 int sz[N];
80 ll k;
81 int n;
82 bool bad[N];
83 pii ord[N];
84 int ans[N];
85
86 void dfs(int v, int par) {
87 sz[v] = 1;
88 for (int u : g[v]) if (u != par) {
89 h[u] = h[v] + 1;
90 dfs(u, v);
91 sz[v] += sz[u];
92 }
93 }
94
95 int main() {
96 startTime = clock();
97 // freopen("input.txt", "r", stdin);
98 // freopen("output.txt", "w", stdout);
99
100 scanf("%d%lld", &n, &k);
101 for (int i = 1; i < n; i++) {
102 int v, u;
103 scanf("%d%d", &v, &u);
104 g[v].push_back(u);
105 g[u].push_back(v);
106 }
107 dfs(1, 0);
108 if (k < n) {
109 printf("No\n");
110 return 0;
111 }
112 for (int v = 1; v <= n; v++) {
113 k -= sz[v];
114 }
115 if (k > 0) {
116 printf("No\n");
117 return 0;
118 }
119 k = -k;
120 int m = 0;
121 for (int v = 2; v <= n; v++)
122 ord[m++] = mp(sz[v], v);
123 sort(ord, ord + m);
124 reverse(ord, ord + m);
125 for (int i = 0; i < m; i++) if (ord[i].first <= k) {
126 k -= ord[i].first;
127 bad[ord[i].second] = 1;
128 }
129 assert(k == 0);
130 m = 0;
131 for (int v = 1; v <= n; v++) if (bad[v]) {
132 ord[m++] = mp(-h[v], v);
133 }
134 for (int v = 1; v <= n; v++) if (!bad[v]) {
135 ord[m++] = mp(h[v], v);
136 }
137 sort(ord, ord + m);
138 for (int i = 0; i < m; i++)
139 ans[ord[i].second] = i + 1;
140 printf("Yes\n");
141 for (int i = 1; i <= n; i++)
142 printf("%d ", ans[i]);
143 printf("\n");
144
145 return 0;
146 }

还有这个大佬，看着像另外一个风格的做法

1 #include <bits/stdc++.h>
2
3 using namespace std;
4
5 typedef long long ll;
6
7 ll n, k;
8 vector<ll> adj[200010];
9 ll a[200010];
10 ll sz[200010];
11 ll f[200010];
12 vector<pair<ll,ll>> t;
13
14 void dfs(ll x, ll p) {
15 sz[x] = 1;
16 for (auto &y : adj[x]) {
17 if (y == p) continue;
18 dfs(y, x);
19 sz[x] += sz[y];
20 }
21 if (x != 1) t.push_back({sz[x], x});
22 }
23
24 void dfs2(ll x, ll p, ll l, ll r) {
25 ll cnt = 0;
26 for (auto &y : adj[x]) {
27 if (y == p) continue;
28 if (f[y]) cnt += sz[y];
29 }
30 a[x] = l + cnt;
31 ll t1 = 0, t2 = 0;
32 for (auto &y : adj[x]) {
33 if (y == p) continue;
34 if (f[y]) {
35 dfs2(y, x, l+t1, l+t1+sz[y]-1);
36 t1 += sz[y];
37 }
38 else {
39 dfs2(y, x, l+cnt+1+t2, l+cnt+t2+sz[y]);
40 t2 += sz[y];
41 }
42 }
43 }
44
45 int main() {
46 ios_base :: sync_with_stdio(false);
47 cin.tie(NULL);
48 cin >> n >> k;
49 for (ll i=0; i<n-1; i++) {
50 ll u, v;
51 cin >> u >> v;
52 adj[u].push_back(v);
53 adj[v].push_back(u);
54 }
55 if (k < n) {
56 cout << "No\n";
57 return 0;
58 }
59 k -= n;
60 dfs(1, 0);
61 sort(t.begin(), t.end());
62 reverse(t.begin(), t.end());
63 for (ll i=0; i<n; i++) {
64 if (k >= t[i].first) {
65 f[t[i].second] = 1;
66 k -= t[i].first;
67 }
68 }
69 if (k) {
70 cout << "No\n";
71 return 0;
72 }
73 dfs2(1, 0, 1, n);
74 cout << "Yes\n";
75 for (ll i=1; i<=n; i++) {
76 cout << n - a[i] + 1 << ' ';
77 }
78 }

类似题目 ABC165_F_LIS_on_Tree
LIS，二分，当前数值修改到这个当下最长子序列对应的位置
树，dfs，当前位置，前修改，最后修改回来

1 #include <cstdio>
2 #include <cstdlib>
3 #include <cstring>
4 #include <cmath>
5 #include <cstdbool>
6 #include <string>
7 #include <algorithm>
8 #include <iostream>
9 #include <sstream>
10 #include <ctime>
11 #include <stack>
12 #include <vector>
13 #include <queue>
14 #include <set>
15 #include <map>
16 using namespace std;
17 #define LL long long
18 #define ULL unsigned long long
19
20 const LL mod_1=1e9+7;
21 const LL mod_2=998244353;
22
23 const double eps_1=1e-5;
24 const double eps_2=1e-10;
25
26 const int maxn=2e5+10;
27
28 int a[maxn], f[maxn], result[maxn], cnt=0;
29
30 vector<int> adj[maxn], child[maxn];
31 bool hap[maxn];
32
33 void find_child(int d)
34 {
35 hap[d]=1;
36 for (auto chi:adj[d])
37 if (!hap[chi])
38 {
39 child[d].push_back(chi);
40 find_child(chi);
41 }
42 }
43
44 void dfs(int d)
45 {
46 int pre_f_ith, pre_cnt = cnt;
47
48 int ith = lower_bound(f, f+cnt, a[d]) - f;
49 pre_f_ith = f[ith];
50 f[ith] = a[d];
51 if (ith>=cnt)
52 cnt++;
53 result[d] = cnt;
54
55 for (auto chi:child[d])
56 dfs(chi);
57
58 cnt = pre_cnt;
59 f[ith] = pre_f_ith;
60 }
61
62 int main()
63 {
64 int n,i,x,y;
65 memset(hap,0,sizeof(hap));
66 scanf("%d",&n);
67 for (i=1;i<=n;i++)
68 scanf("%d",&a[i]);
69 for (i=1;i<n;i++)
70 {
71 scanf("%d%d",&x,&y);
72 adj[x].push_back(y);
73 adj[y].push_back(x);
74 }
75
76 f[0]=0;
77 find_child(1);
78 dfs(1);
79
80 for (i=1;i<=n;i++)
81 printf("%d\n",result[i]);
82
83 return 0;
84 }
85 /*
86 5
87 1 2 3 4 5
88 1 2
89 2 3
90 3 4
91 4 5
92
93
94 5
95 5 4 3 2 1
96 1 2
97 2 3
98 3 4
99 4 5
100
101 1
102 1
103
104 5
105 10 10 10 10 10
106 1 2
107 2 3
108 3 4
109 4 5
110
111
112 7
113 7 9 9 11 11 10 10
114 1 2
115 2 3
116 3 4
117 4 5
118 5 6
119 6 7
120
121 */