简答题 偏难
#23312

树的重心 小简单正在学习离散数学,今天的内容是图论基础,在课上他做了如下两条笔记: 1.一个大小为n的树由n个结点与n-1条无向边构成,且满足任意两个结点间有…

树的重心

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

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>
这道题暂未补解析。