codeforces1528c_us open of surfing

codeforces1528c_us open of surfingCodeForces 1073F Choosing Two Paths

大家好,又见面了,我是你们的朋友全栈君。

Description

You are given an undirected unweighted tree consisting of \(n\) vertices.

An undirected tree is a connected undirected graph with \(n−1\) edges.

Your task is to choose two pairs of vertices of this tree (all the chosen vertices should be distinct) \((x_1,y_1)\) and \((x_2,y_2)\) in such a way that neither \(x_1\) nor \(y_1\) belong to the simple path from \(x_2\) to \(y_2\) and vice versa (neither \(x_2\) nor \(y_2\) should not belong to the simple path from \(x_1\) to \(y_1\)).

It is guaranteed that it is possible to choose such pairs for the given tree.

Among all possible ways to choose such pairs you have to choose one with the maximum number of common vertices between paths from \(x_1\) to \(y_1\) and from \(x_2\) to \(y_2\). And among all such pairs you have to choose one with the maximum total length of these two paths.

It is guaranteed that the answer with at least two common vertices exists for the given tree.

The length of the path is the number of edges in it.

The simple path is the path that visits each vertex at most once.

Input

The first line contains an integer \(n\) — the number of vertices in the tree \((6 \le n \le 2 \cdot 10^5)\).

Each of the next \(n−1\) lines describes the edges of the tree.

Edge \(i\) is denoted by two integers \(u_i\) and \(v_i\), the labels of vertices it connects \((1\le u_i,v_i\le n, u_i \neq v_i)\).

It is guaranteed that the given edges form a tree.

It is guaranteed that the answer with at least two common vertices exists for the given tree.

Output

Print any two pairs of vertices satisfying the conditions described in the problem statement.

It is guaranteed that it is possible to choose such pairs for the given tree.

Examples

Input

7
1 4
1 5
1 6
2 3
2 4
4 7

Output

3 6
7 5

Input

9
9 3
3 5
1 2
4 3
4 7
1 7
4 6
3 8

Output

2 9
6 8

Input

10
6 8
10 3
3 7
5 8
1 7
7 2
2 9
2 8
1 4

Output

10 6
4 5

Input

11
1 2
2 3
3 4
1 5
1 6
6 7
5 8
5 9
4 10
4 11

Output

9 11
8 10

Note

The picture corresponding to the first example:

img

The intersection of two paths is \(2\) (vertices \(1\) and \(4\)) and the total length is \(4+3=7\).

The picture corresponding to the second example:

img

The intersection of two paths is \(2\) (vertices \(3\) and \(4\)) and the total length is \(5+3=8\).

The picture corresponding to the third example:

img

The intersection of two paths is \(3\) (vertices \(2\), \(7\) and \(8\)) and the total length is \(5+5=10\).

The picture corresponding to the fourth example:

img

The intersection of two paths is \(5\)(vertices \(1\), \(2\), \(3\), \(4\) and \(5\)) and the total length is \(6+6=12\).

Solution

题意:给定一棵树,找两组点\((x_1, y_1)\)\((x_2, y_2)\),使得\(x_1,y_1\)不在\(x_2\)\(y_2\)之间的路径上,\(x_2,y_2\)不在\(x_1\)\(y_1\)之间的路径上,要求:

  • \(x_1,y_1\)之间的路径与\(x_2,y_2\)之间的路径的重合边数最多
  • 满足第一个条件的前提下,两条路径的长度之和最大

我们考虑两条路径的公共路径,不妨记作\((x, y)\)\(x\)\(y\)的LCA记作\(a\),则\(a\)或者是\(x\)\(y\)中的一个,或者是\(x\)\(y\)路径上的其他节点,所以我们先求出每个点的度大于2的后代的最大深度,以及每个点往父亲方向能够到达的最远距离,然后再一次DFS,对于任何一个点\(u\)

  • 如果\(u\)有两个孩子节点具有度大于2的后代,则尝试更新答案
  • 否则,若\(u\)只有一个孩子节点具有度大于2的后代,且\(u\)自身的度大于2,则尝试更新答案
#include <bits/stdc++.h> using namespace std; const int maxn = 200011; struct triple { triple(int _u = 0, int _v1 = 0, int _v2 = 0) : u(_u), v1(_v1), v2(_v2) {} int u, v1, v2; bool operator<(const triple &b) const {return u < b.u;} }; vector<int> w[maxn]; int deg[maxn], dep[maxn]; int x1, y1, x2, y2; pair<pair<int, int>, triple> val[maxn]; // <<deg=3的后代(u)的最大深度, u到两个最远后代(v1, v2)的距离之和>, <u, v1, v2>> pair<int, int> ans; pair<int, int> mxdep[maxn], updis[maxn]; // <最远距离, u> vector<pair<pair<int, int>, int>> downdis[maxn]; // <<后代(u)的最大深度, u>, 到该后代的路径上的第一个点> void dfs1(int u, int d, int pre) { dep[u] = d; mxdep[u] = make_pair(d, u); for (int v : w[u]) { if (v == pre) continue; dfs1(v, d + 1, u); mxdep[u] = max(mxdep[u], mxdep[v]); downdis[u].push_back(make_pair(mxdep[v], v)); } sort(downdis[u].begin(), downdis[u].end(), greater<pair<pair<int, int>, int>>()); } void dfs2(int u, int pre) { if (~pre) { updis[u] = make_pair(1 + updis[pre].first, updis[pre].second); auto tp = downdis[pre][0].second == u ? downdis[pre][1].first : downdis[pre][0].first; if (downdis[pre].size() > 1) { updis[u] = max(updis[u], make_pair(tp.first + 1, tp.second)); } } else { updis[u] = make_pair(0, u); } for (int v : w[u]) { if (v == pre) continue; dfs2(v, u); } } void dfs3(int u, int pre) { vector<pair<pair<pair<int, int>, triple>, int>> vec; for (int v : w[u]) { if (v == pre) continue; dfs3(v, u); if (val[v].first.first) { vec.push_back(make_pair(val[v], v)); } } if (vec.size() >= 2) { sort(vec.begin(), vec.end(), greater<pair<pair<pair<int, int>, triple>, int>>()); auto &x = vec[0].first, &y = vec[1].first; val[u] = x; int a = x.first.first + y.first.first - 2 * dep[u]; int b = x.first.second + y.first.second; auto c = make_pair(a, b); if (c > ans) { ans = c; x1 = x.second.v1, y1 = y.second.v1; x2 = x.second.v2, y2 = y.second.v2; } } else { if (vec.size() == 1) { val[u] = vec[0].first; } else if (deg[u] >= 3) { assert(downdis[u].size() >= 2); auto &x = downdis[u][0].first, &y = downdis[u][1].first; int tp = x.first + y.first - 2 * dep[u]; val[u] = make_pair(make_pair(dep[u], tp), triple(u, x.second, y.second)); } else { val[u] = make_pair(make_pair(0, 0), triple()); } if (vec.size() == 1 && deg[u] >= 3) { vector<pair<int, int>> cand; cand.push_back(updis[u]); int up = min(3, (int)downdis[u].size()); for (int i = 0; i < up; ++i) { if (downdis[u][i].second == vec[0].second) continue; cand.push_back(downdis[u][i].first); } assert(cand.size() >= 2); sort(cand.begin(), cand.end(), greater<pair<int, int>>()); auto &x = vec[0].first; int a = x.first.first - dep[u]; int b = x.first.second + cand[0].first + cand[1].first; auto c = make_pair(a, b); if (c > ans) { ans = c; x1 = x.second.v1, y1 = cand[0].second; x2 = x.second.v2, y2 = cand[1].second; } } } } int main() { int n; scanf("%d", &n); for (int i = 1; i < n; ++i) { int u, v; scanf("%d%d", &u, &v); w[u].push_back(v); w[v].push_back(u); ++deg[u]; ++deg[v]; } ans = make_pair(0, 0); dfs1(1, 0, -1); dfs2(1, -1); dfs3(1, -1); printf("%d %d\n%d %d\n", x1, y1, x2, y2); return 0; }

转载于:https://www.cnblogs.com/hitgxz/p/9977668.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107195.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 以管理员身份修改hosts文件_如何修改hosts文件权限

    以管理员身份修改hosts文件_如何修改hosts文件权限第一步先在目录C:\Windows\System32\drivers\etc下找到host文件。右键点开属性,取消勾选只读。进入“安全”点击编辑选择允许修改。以管理员身份运行powershell,输入指令cddrivers\etc跳转到该目录下,再输入指令notepadhosts回车弹出host文件窗…

    2022年10月12日
  • jsonobject转string数组_jsonobject.parsearray

    jsonobject转string数组_jsonobject.parsearray1.String转JSONObjectStringjsonMessage=”{\”语文\”:\”88\”,\”数学\”:\”78\”,\”计算机\”:\”99\”}”;JSONObject myJson=JSONObject.fromObject(jsonMessage);2.String转JSONArrayStringjsonMessage=”[{‘nu

  • tabnine 激活码【2021免费激活】

    (tabnine 激活码)这是一篇idea技术相关文章,由全栈君为大家提供,主要知识点是关于2021JetBrains全家桶永久激活码的内容https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~DB847YMYYZ-eyJsaWNlb…

  • JVM内存结构面试问题及解答[通俗易懂]

    JVM内存结构面试问题及解答[通俗易懂]以下是jvm内存的常见面试问题:1、JVM管理的内存结构是怎样的?2、不同的虚拟机在实现运行时内存的时候有什么区别?3、运行时数据区中哪些区域是线程共享的?哪些是独享的?4、除了JVM运行时内存以外,还有什么区域可以用吗?5、堆和栈的区别是什么?6、Java中的数组是存储在堆上还是栈上的?7、Java中的对象创建有多少种方式?8、Java中对象创建的过程是怎么样的?9、Java…

  • python神经网络图像识别note

    python神经网络图像识别noteBP神经网络手写数字识别mnist测试集(28*28)识别mnist训练集60000个样本,测试集10000个样本,发现使用4层BP神经网络784,50,20,10没有3层神经网络784,100,10识别率高.只有88%左右对自己手写的样本更差.先是处理了手写样本的背景色噪声,但是仍然很差,估计1.mnist训练集中对数字图像位置进行了居中,大小进行了统一,自己手写的样本没有做相应…

  • mysql中左连接查询_mysql左连接「建议收藏」

    mysql中左连接查询_mysql左连接「建议收藏」1.on后面的条件和where后面的条件的区别查询语句开始会根据on后面的条件创建一张虚拟表,左边表是全部数据,右边表会根据on后面的条件进行筛选。然后再根据where后面的条件进行筛选虚拟表中的数据作为最终数据所以如果是筛选右表中的条件放在了where中则则会过滤掉部分左表中的数据结论:筛选右表的条件和左右表关联的条件写在on中筛选左表的条件写在where中2.右表中的条件放在…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号