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)


相关推荐

  • IPtables中SNAT、DNAT和MASQUERADE的含义

    IPtables中SNAT、DNAT和MASQUERADE的含义IPtables中可以灵活的做各种网络地址转换(NAT),网络地址转换主要有两种:SNAT和DNAT。SNAT是sourcenetworkaddresstranslation的缩写,即源地址目标转换。比如,多个PC机使用ADSL路由器共享上网,每个PC机都配置了内网IP,PC机访问外部网络的时候,路由器将数据包的报头中的源地址替换成路由器的ip,当外部网络的服务器比如网站web服务器接到访

  • pycharm报错traceback most_cm3d2报错error

    pycharm报错traceback most_cm3d2报错errorPycharm报错Pythonerror:PermissionError:[Errno13]Permissiondenied:在pycharm中读取csv文件时,出现错误PermissionError:[Errno13]Permissiondenied:。看了大部分博客说是因为文件权限问题,或者文件被手动打开,这两个方法都试了试后,无效。解决问题的方法:配置Python编译器时将ScriptPath的路径写到脚本的具体路径,要包含脚本的文件名。如下图。…

  • 2021年 github被墙最新hosts-每日更新[通俗易懂]

    2021年 github被墙最新hosts-每日更新[通俗易懂]2021年github被墙最新hosts-每日更新解决方法参考链接:http://blog.yoqi.me/lyq/16489.html

  • oracle如何修改用户密码_oracle重置用户名密码

    oracle如何修改用户密码_oracle重置用户名密码轻松搞定Oracle用户密码修改 摘要:服务器更换、数据库移植都会涉及到Oracle用户密码的修改操作,这里给出几段简单的代码,帮您轻松搞定Oracle用户密码的修改操作。 我们假设这样一个应用场景,数据库需要移植,库中某一个用户的Oracle用户密码不知道,可是这个密码因为在其他程序中使用了而不能修改,在新的数据库系统中,这

  • webbench源码分析_webpack原理和机制

    webbench源码分析_webpack原理和机制webbench是一种网站的压力测试工具,它是由Lionbridge公司开发,wenbench的标准测试可以向我们展示两项内容:每秒钟相应的请求数和每秒钟传输的数据量;。webbench不但能具有便准静态页面的测试能力,还能对动态页面(ASP,PHP,Java,CGI)进行测试的能力。还有就是他支持对含有SSL的安全网站例如电子商务网站进行静态或动态的性能测试。Webbench最多可以模拟3

  • eric6教程(电脑的配置基本知识)

    欢迎加入QQ群:853840665,一块学习讨论单击菜单栏Setting-&gt;Preferences,进入设置界面 下面从上而下设置比较常用的设置,其他的各位可以自行研究1.设置编译器2.设置API3设置自动补全4.设置自动检查时间间隔默认是5S,我在用的时候发现经常代码该正确了,却还是提示错误,这里把时间改短5.设置字体大小…

发表回复

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

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