首页 › 试卷 › 信息学奥赛 › 信息学奥赛-提高级 › 全国信息学奥林匹克联赛(NOIP2019)复赛 提高组 day2

全国信息学奥林匹克联赛(NOIP2019)复赛 提高组 day2 VIP

信息学奥赛-提高级 共 3 题 含标准答案与解析
返回试卷列表
本页为整卷浏览:先自己做一遍,再展开「查看答案与解析」核对。

一、简答题

1. 简答题

Emiya家今天的饭

【题目描述】

Emiya 是个擅长做菜的高中生,他共掌握 n 种烹饪方法,且会使用 m 种主要食材做菜。为了方便叙述,我们对烹饪方法从 1~n 编号,对主要食材从 1 ~m 编号。

Emiya 做的每道菜都将使用恰好一种烹饪方法与恰好一种主要食材。更具体地,Emiya 会做 ai,j 道不同的使用烹饪方法 i 和主要食材 j 的菜(1 ≤i≤n,1≤j≤m),这也意味着 Emiya 总共会做

道不同的菜。

Emiya 今天要准备一桌饭招待 Yazid 和 Rin 这对好朋友,然而三个人对菜的搭配有不同的要求,更具体地,对于一种包含 k 道菜的搭配方案而言:

(1)Emiya 不会让大家饿肚子,所以将做至少一道菜,即 k≥1

(2)Rin 希望品尝不同烹饪方法做出的菜,因此她要求每道菜的烹饪方法互不相同

(3)Yazid 不希望品尝太多同一食材做出的菜,因此他要求每种主要食材至多在一半的菜(即道菜)中被使用

这里的⌊x⌋ 为下取整函数,表示不超过 x 的最大整数。

这些要求难不倒 Emiya,但他想知道共有多少种不同的符合要求的搭配方案。两种方案不同,当且仅当存在至少一道菜在一种方案中出现,而不在另一种方案中出现。

Emiya 找到了你,请你帮他计算,你只需要告诉他符合所有要求的搭配方案数对质数998,244,353 取模的结果。

【输入格式】

从文件meal.in中读入数据。

第 1 行两个用单个空格隔开的整数 n,m。

第 2 行至第 n+1 行,每行 m 个用单个空格隔开的整数,其中第 i + 1行的 m 个数依次为 ai,1,ai,2,⋯,ai,m。

【输出格式】

输出到文件meal.out中。

仅一行一个整数,表示所求方案数对 998,244,353 取模的结果。

【样例 1 输入】

2 3 

1 0 1

0 1 1

【样例 1 输出】

3

【样例1解释】

由于在这个样例中,对于每组i,j,Emiya都最多只会做一道菜,因此我们直接通 过给出烹饪方法、主要食材的编号来描述一道菜。

符合要求的方案包括:

•做一道用烹饪方法1、主要食材1的菜和一道用烹饪方法2、主要食材2的菜

•做一道用烹饪方法1、主要食材1的菜和一道用烹饪方法2、主要食材3的菜

•做一道用烹饪方法1、主要食材3的菜和一道用烹饪方法2、主要食材2的菜

 因此输出结果为3 mod 998,244,353 = 3。

需要注意的是,所有只包含一道菜的方案都是不符合要求的,因为唯一的主要食材 在超过一半的菜中出现,这不满足Yazid的要求。

【样例2输入】

3 3

1 2 3

4 5 0

6 0 0

【样例2输出】

190

【样例2解释】

Emiya必须至少做2道菜。

做2道菜的符合要求的方案数为100。

做3道菜的符合要求的方案数为90。

因此符合要求的方案数为100 + 90 = 190。

【样例3输入】

5 5

1 0 0 1 1

0 1 0 1 0

1 1 1 1 0

1 0 1 0 1

0 1 1 0 1

【样例3输出】

742

【数据范围】

对于所有测试点,保证 1 ≤n≤ 100, 1 ≤ m ≤ 2000, 0≤ai,j< 998,244,353。

查看答案与解析
答案:<p style="text-align: left;">#include &lt;iostream&gt;</p><p style="text-align: left;">#include &lt;cstdlib&gt;</p><p style="text-align: left;">#include &lt;cstring&gt;</p><p style="text-align: left;">#include &lt;cstdio&gt;</p><p style="text-align: left;">#define mod 998244353</p><p> </p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">typedef long long ll;</p><p style="text-align: left;">const int MAXN = 105, MAXM = 2005;</p><p style="text-align: left;">int n,m,a[MAXN][MAXM],sum[MAXN][MAXM];</p><p style="text-align: left;">ll f[MAXN][MAXN*2],g[MAXN][MAXN];</p><p> </p><p style="text-align: left;">int main()</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>cin &gt;&gt; n &gt;&gt; m;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = 1; i&lt;=n; i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>    for(int j = 1; j&lt;=m; j++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>    {</p><p style="text-align: left;"><span style="white-space:pre"> </span>        scanf("%d",&amp;a[i][j]);</p><p style="text-align: left;"><span style="white-space:pre"> </span>        sum[i][0] = (sum[i][0]+a[i][j])%mod;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;">    for(int i = 1; i&lt;=n; i++)</p><p style="text-align: left;">        for(int j = 1; j&lt;=m; j++)</p><p style="text-align: left;">            sum[i][j] = (sum[i][0]-a[i][j]+mod)%mod;</p><p style="text-align: left;">    ll ans = 0;</p><p style="text-align: left;">    for(int col = 1; col&lt;=m; col++)</p><p style="text-align: left;">    {</p><p style="text-align: left;">        memset(f,0,sizeof(f));</p><p style="text-align: left;">        f[0][n] = 1;</p><p style="text-align: left;">        for(int i = 1; i&lt;=n; i++)</p><p style="text-align: left;">            for(int j = n-i; j&lt;=n+i; j++) </p><p style="text-align: left;">                f[i][j] = (f[i-1][j]+f[i-1][j-1]*a[i][col]%mod+f[i-1][j+1]*sum[i][col]%mod)%mod;</p><p style="text-align: left;">        for(int j = 1; j&lt;=n; j++)</p><p style="text-align: left;">            ans = (ans+f[n][n+j])%mod;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>g[0][0] = 1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = 1; i&lt;=n; i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>    for(int j = 0; j&lt;=n; j++) </p><p style="text-align: left;"><span style="white-space:pre"> </span>    g[i][j] = (g[i-1][j]+(j&gt;0?g[i-1][j-1]*sum[i][0]%mod:0))%mod;</p><p style="text-align: left;">    for(int j = 1; j&lt;=n; j++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>    ans = (ans-g[n][j]+mod)%mod;  </p><p style="text-align: left;"><span style="white-space:pre"> </span>cout &lt;&lt; ans*(mod-1)%mod &lt;&lt; endl;</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。
2. 简答题

划分

【题目描述】

2048年,第三十届CSP认证的考场上,作为选手的小明打开了第一题。这个题的 样例有n组数据,数据从1~n编号,i号数据的规模为ai。

小明对该题设计出了一个暴力程序,对于一组规模为u的数据,该程序的运行时 间为u^2。然而这个程序运行完一组规模为u的数据之后,它将在任何一组规模小于u 的数据上运行错误。样例中的ai,不一定递增,但小明又想在不修改程序的情况下正确 运行样例,于是小明决定使用一种非常原始的解决方案:将所有数据划分成若干个数据 段,段内数据编号连续,接着将同一段内的数据合并成新数据,其规模等于段内原数据 的规模之和.小明将让新数据的规模能够递增。

也就是说,小明需要找到一些分界点使得

注意P可以为0且此时k0 = 0,也就是小明可以将所有数据合并在一起运行。

小明希望他的程序在正确运行样例情况下,运行时间也能尽量小,也就是最小化

小明觉得这个问题非常有趣,并向你请教:给定n和ai,请你求出最优划分方案 下,小明的程序的最小运行时间。

【输入格式】

从文件partition.in中读入数据。

由于本题的数据范围较大,部分测试点的ai将在程序内生成。

第一行两个整数n.type. n的意义见题目描述,type表示输入方式。

1.若type = 0.则该测试点的ai直接给出。输入文件接下来:第二行n个以空格 分隔的整数ai,表示每组数据的规模。

2.若type = 1则该测试点的ai将特殊生成,生成方式见后文。输入文件接下来: 第二行六个以空格分隔的整数x,y,z,b1,b2,m。 接下来m行中,第i行包含三个以空格分隔的正整数pi,li,ri。

对于type = 1的23 ~ 25号测试点,ai的生成方式如下:

给定整数x,y,z,b1,b2,m,以及m个三元组(pi,li,ri)。

保证 n2。 若 n > 2,则

保证

对于所有则有ai=(bi   mod(rj-lj+1))+lj

上述数据生成方式仅是为了减少输入量大小,标准算法不依赖于该生成方式。

【输出格式】

输出到文件partition.out中。

输出一行一个整数,表示答案。

【样例1输入】

5 0

5 17 9 9

【样例1输出】

247

【样例1解释】

最优的划分方案为{5,1},{7},{9},{9}。由5 + 1<=7<=9<=9知该方案合法。

答案为(5 + 1)^2 + 7^2 + 9^2 + 9^2 = 247。

虽然划分方案{5},{1},{7},{9},{9}对应的运行时间比247小,但它不是一组合法 方案,因为5>1。

虽然划分方案{5},{1,7},{9},{9}合法,但该方案对应的运行时间为251,比247大。

【样例2输入】

10 0

5677462 13 19 9

【样例2输出】

1256

【样例2解释】

最优的划分方案为{5},{6},{7},{7},{4,6,2},{13},{19,9}。

【数据范围】

所有测试点满足:type € {0,1} , 2 < =n <= 4 x 10^7 , 1 < =ai,<= 10^9 , 1 <=m < =10^5 , 1 < =li <= ri <= 10^9 , 0 < x,y,z,b1,b2 < 2^30。

查看答案与解析
答案:<p style="text-align: left;">#include&lt;bits/stdc++.h&gt;</p><p style="text-align: left;">using namespace std ;</p><p style="text-align: left;">const int N = 4e7 + 10 ;</p><p style="text-align: left;">const int M = 1e5 + 10 ;</p><p style="text-align: left;">const int mod = (1 &lt;&lt; 30) ;</p><p style="text-align: left;">int n , type , x , y , z , m ;</p><p style="text-align: left;">int a[N] , b[N] , p[M] , l[M] , r[M] , q[N] , pre[N] ;</p><p style="text-align: left;">long long sum[N] ;</p><p style="text-align: left;">inline long long d(int x) { return sum[x] - sum[pre[x]] ; }</p><p style="text-align: left;">signed main() {</p><p style="text-align: left;">  ios :: sync_with_stdio(false) ; cin.tie(nullptr) ; cout.tie(nullptr) ;</p><p style="text-align: left;">  cin &gt;&gt; n &gt;&gt; type ;</p><p style="text-align: left;">  if(type) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>cin &gt;&gt; x &gt;&gt; y &gt;&gt; z &gt;&gt; b[1] &gt;&gt; b[2] &gt;&gt; m ;</p><p style="text-align: left;">    for(register int i = 1 ; i &lt;= m ; i ++) { cin &gt;&gt; p[i] &gt;&gt; l[i] &gt;&gt; r[i] ; }</p><p style="text-align: left;">    for(register int i = 3 ; i &lt;= n ; i ++) { b[i] = (0ll + 1ll * b[i - 1] * x + 1ll * b[i - 2] * y + z) % mod ; }</p><p style="text-align: left;">    for(register int i = 1 ; i &lt;= m ; i ++)</p><p style="text-align: left;">      for(register int j = p[i - 1] + 1 ; j &lt;= p[i] ; j ++) { a[j] = (b[j] % (r[i] - l[i] + 1)) + l[i] ; sum[j] = sum[j - 1] + a[j] ; }</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;">  else {</p><p style="text-align: left;">  <span style="white-space:pre"> </span>for(register int i = 1 ; i &lt;= n ; i ++) { cin &gt;&gt; a[i] ; sum[i] = sum[i - 1] + a[i] ; }</p><p style="text-align: left;"><span style="white-space:pre"> </span>} int h , t ; q[h = t = 0] = 0 ;</p><p style="text-align: left;">  for(register int i = 1 ; i &lt;= n ; i ++) {</p><p style="text-align: left;">    while(h &lt; t &amp;&amp; d(q[h + 1]) + sum[q[h + 1]] &lt;= sum[i]) ++ h ; </p><p style="text-align: left;"><span style="white-space:pre"> </span>pre[i] = q[h] ;</p><p style="text-align: left;">    while(h &lt; t &amp;&amp; d(q[t]) + sum[q[t]] &gt;= d(i) + sum[i]) -- t ;</p><p style="text-align: left;">    q[++ t] = i ;</p><p style="text-align: left;">  }  int now = n ; __int128 ans = 0 , tmp = 1 ;</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(now) { tmp = d(now) ; tmp *= d(now) ; ans += tmp ; now = pre[now] ; }</p><p style="text-align: left;"><span style="white-space:pre"> </span>int st[50] , tp = 0 ;</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(ans) { st[++ tp] = ans % 10 ; ans /= 10 ; }</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(tp) { cout &lt;&lt; st[tp --] ; }</p><p style="text-align: left;">  return 0 ;</p><p style="text-align: left;">}</p>
这道题暂未补解析。
3. 简答题

树的重心

小简单正在学习离散数学,今天的内容是图论基础,在课上他做了如下两条笔记:

1.一个大小为n的树由n个结点与n-1条无向边构成,且满足任意两个结点间有 且仅有一条简单路径。在树中删去一个结点及与它关联的边,树将分裂为若干个 子树;而在树中删去一条边(保留关联结点,下同),树将分裂为恰好两个子树。

2.对于一个大小为n的树与任意一个树中结点c,称c是该树的重心当且仅当在树 中删去c及与它关联的边后,分裂出的所有子树的大小均不超过(其中Lx」 是下取整函数)。对于包含至少一个结点的树.它的重心只可能有1或2个。

课后老师给出了一个大小为n的树S,树中结点从1~n编号。小简单的课后作业 是求出S单独删去每条边后,分裂出的两个子树的重心编号和之和。即:

上式中,E表示树S的边集,(u,n)表示一条连接u号点和V号点的边。S'u与S'v 分别表示树S删去边(u,v)后,u号点与V号点所在的被分裂出的子树。

小简单觉得作业并不简单,只好向你求助,请你教教他。

【输入格式】

从文件centroid.in中读入数据。

本题输入包含多组测试数据。

第一行一个整数T表示数据组数。

接下来依次给岀每组输入数据,对于每组数据:

第一行一个整数n表示树S的大小。

接下来n -1行,每行两个以空格分隔的整数 ui,vi,表示树中的一条边(ui,vi)。

【输出格式】

输出到文件centroid.out中。

共T行,每行一个整数.第i行的整数表示:第i组数据给岀的树单独删去每条边 后,分裂出的两个子树的重心编号和之和。

【样例1输入】

2

5

12

23

24

35

7

1 2

1 3

1 4

3 5

3 6

6 7

【样例1输出】

32

56

【样例1解释】

对于第一组数据:

删去边(1,2), 1号点所在子树重心编号为{1}, 2号点所在子树重心编号为{2,3}。 删去边(2,3), 2号点所在子树重心编号为⑵,3号点所在子树重心编号为{3,5}。

删去边(2,4), 2号点所在子树重心编号为{2,3}, 4号点所在子树重心编号为{4}。 删去边(3,5), 3号点所在子树重心编号为{2}, 5号点所在子树重心编号为{5}。

因此答案为 1 + 2 + 3 + 2 + 3 + 5 + 2 + 3 + 4 + 2 + 5 = 32。

【数据范围】

表中特殊性质一栏,两个变量的含义为存在一个1~n的排列使得: 

A:树的形态是一条链。即存在一条边(pi,pi+1)。

B:树的形态是一个完美二叉树。即存在两条边(Pi,P2i)与(Pi,P2i+1)。 对于所有测试点:保证给岀的图是一个树。

查看答案与解析
答案:<p style="text-align: left;">#include &lt;cstdio&gt;</p><p style="text-align: left;">#include &lt;algorithm&gt;</p><p style="text-align: left;">using namespace std;</p><p><br style="text-align: left;"/></p><p style="text-align: left;">const int Maxn = 300000;</p><p style="text-align: left;">const int Maxlog = 19;</p><p style="text-align: left;">typedef long long ll;</p><p><br style="text-align: left;"/></p><p style="text-align: left;">#ifdef LOACL</p><p style="text-align: left;">bool ___;</p><p style="text-align: left;">#endif</p><p><br style="text-align: left;"/></p><p style="text-align: left;">struct Edge {</p><p style="text-align: left;"><span style="white-space:pre"> </span>int to;</p><p style="text-align: left;"><span style="white-space:pre"> </span>Edge *nxt;</p><p style="text-align: left;">};</p><p style="text-align: left;">Edge pool[Maxn * 2 + 5];</p><p style="text-align: left;">Edge *G[Maxn + 5], *ecnt;</p><p style="text-align: left;">inline void addedge(int u, int v) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>Edge *p = ++ecnt;</p><p style="text-align: left;"><span style="white-space:pre"> </span>p-&gt;to = v, p-&gt;nxt = G[u];</p><p style="text-align: left;"><span style="white-space:pre"> </span>G[u] = p;</p><p style="text-align: left;">}</p><p><br style="text-align: left;"/></p><p style="text-align: left;">int N;</p><p style="text-align: left;">int siz[Maxn + 5];</p><p style="text-align: left;">int mxson[Maxn + 5], mx2son[Maxn + 5];</p><p style="text-align: left;">ll ans;</p><p><br style="text-align: left;"/></p><p style="text-align: left;">int s[Maxn + 1][Maxlog + 2];</p><p style="text-align: left;">int f[Maxn + 5];</p><p><br style="text-align: left;"/></p><p style="text-align: left;">inline void clear() {</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = 1; i &lt;= N; i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>mxson[i] = mx2son[i] = 0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = 1; i &lt;= N; i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int j = 0; j &lt;= Maxlog; j++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>s[i][j] = 0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = 1; i &lt;= N; i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>G[i] = NULL;</p><p style="text-align: left;"><span style="white-space:pre"> </span>ecnt = &amp;pool[0];</p><p style="text-align: left;"><span style="white-space:pre"> </span>ans = 0;</p><p style="text-align: left;">}</p><p style="text-align: left;">inline void modify(int u) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = 1; i &lt;= Maxlog; i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>s[u][i] = s[s[u][i - 1]][i - 1];</p><p style="text-align: left;">}</p><p style="text-align: left;">void PreDFS(int u, int fa) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>siz[u] = 1, f[u] = fa;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(Edge *p = G[u]; p != NULL; p = p-&gt;nxt) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>int v = p-&gt;to;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(v == fa) continue;</p><p style="text-align: left;"><span style="white-space:pre"> </span>PreDFS(v, u);</p><p style="text-align: left;"><span style="white-space:pre"> </span>siz[u] += siz[v];</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(siz[v] &gt; siz[mxson[u]]) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>mx2son[u] = mxson[u];</p><p style="text-align: left;"><span style="white-space:pre"> </span>mxson[u] = v;</p><p style="text-align: left;"><span style="white-space:pre"> </span>} else if(siz[v] &gt; siz[mx2son[u]])</p><p style="text-align: left;"><span style="white-space:pre"> </span>mx2son[u] = v;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>s[u][0] = mxson[u];</p><p style="text-align: left;"><span style="white-space:pre"> </span>modify(u);</p><p style="text-align: left;">}</p><p style="text-align: left;">inline void calc(int u) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>int tot = siz[u], rt = u;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = Maxlog; i &gt;= 0; i--)</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(tot - siz[s[u][i]] &lt;= tot / 2)</p><p style="text-align: left;"><span style="white-space:pre"> </span>u = s[u][i];</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(siz[s[u][0]] &lt;= tot / 2) ans += u;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(u != rt &amp;&amp; siz[u] &lt;= tot / 2) ans += f[u];</p><p style="text-align: left;">}</p><p style="text-align: left;">void DFS(int u, int fa) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(fa != 0) calc(fa), calc(u);</p><p style="text-align: left;"><span style="white-space:pre"> </span>int flag = 0, t1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(N - siz[u] &gt; siz[mxson[u]]) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>t1 = mx2son[u], flag = 1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>mx2son[u] = mxson[u], mxson[u] = fa;</p><p style="text-align: left;"><span style="white-space:pre"> </span>} else if(N - siz[u] &gt; siz[mx2son[u]]){</p><p style="text-align: left;"><span style="white-space:pre"> </span>t1 = mx2son[u], flag = 2;</p><p style="text-align: left;"><span style="white-space:pre"> </span>mx2son[u] = fa;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(Edge *p = G[u]; p != NULL; p = p-&gt;nxt) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>int v = p-&gt;to;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(v == fa) continue;</p><p style="text-align: left;"><span style="white-space:pre"> </span>siz[u] += siz[fa] - siz[v], f[u] = v;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(v == mxson[u]) s[u][0] = mx2son[u];</p><p style="text-align: left;"><span style="white-space:pre"> </span>else s[u][0] = mxson[u];</p><p style="text-align: left;"><span style="white-space:pre"> </span>modify(u);</p><p style="text-align: left;"><span style="white-space:pre"> </span>DFS(v, u);</p><p style="text-align: left;"><span style="white-space:pre"> </span>siz[u] -= siz[fa] - siz[v], f[u] = fa;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(flag == 1) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>mxson[u] = mx2son[u], mx2son[u] = t1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>} else if(flag == 2) mx2son[u] = t1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>s[u][0] = mxson[u];</p><p style="text-align: left;"><span style="white-space:pre"> </span>modify(u);</p><p style="text-align: left;">}</p><p><br style="text-align: left;"/></p><p style="text-align: left;">#ifdef LOACL</p><p style="text-align: left;">bool ____;</p><p style="text-align: left;">#endif</p><p><br style="text-align: left;"/></p><p style="text-align: left;">int main() {</p><p style="text-align: left;">#ifdef LOACL</p><p style="text-align: left;"><span style="white-space:pre"> </span>freopen("in.txt", "r", stdin);</p><p style="text-align: left;"><span style="white-space:pre"> </span>freopen("out.txt", "w", stdout);</p><p style="text-align: left;">#endif</p><p style="text-align: left;"><span style="white-space:pre"> </span>int _;</p><p style="text-align: left;"><span style="white-space:pre"> </span>scanf("%d", &amp;_);</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(_--) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>scanf("%d", &amp;N);</p><p style="text-align: left;"><span style="white-space:pre"> </span>clear();</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = 1; i &lt; N; i++) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>int u, v;</p><p style="text-align: left;"><span style="white-space:pre"> </span>scanf("%d %d", &amp;u, &amp;v);</p><p style="text-align: left;"><span style="white-space:pre"> </span>addedge(u, v), addedge(v, u);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>PreDFS(1, 0);</p><p style="text-align: left;"><span style="white-space:pre"> </span>DFS(1, 0);</p><p style="text-align: left;"><span style="white-space:pre"> </span>printf("%lld\n", ans);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;">#ifdef LOACL</p><p style="text-align: left;"><span style="white-space:pre"> </span>printf("%.2f\n", (&amp;____ - &amp;___) / 1048576.0);</p><p style="text-align: left;">#endif</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。