Submission #9640338 - AtCoder Grand Contest 005
// ===================================
// author: M_sea
// website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;
inline int read()
{
int X = 0, w = 1;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
w = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
X = X * 10 + c - '0', c = getchar();
return X * w;
}
const int N = 1000000 + 10;
struct Tree
{
struct edge
{
int v, nxt;
} e[N << 1];
int head[N];
inline void addEdge(int u, int v)
{
static int cnt = 0;
e[++cnt] = (edge){v, head[u]}, head[u] = cnt;
}
int dep[N], sz[N], fa[N], hson[N], top[N];
inline void dfs1(int u, int f)
{
dep[u] = dep[fa[u] = f] + 1, sz[u] = 1;
for (re int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v;
if (v == f)
continue;
dfs1(v, u), sz[u] += sz[v];
if (sz[v] > sz[hson[u]])
hson[u] = v;
}
}
inline void dfs2(int u, int anc)
{
top[u] = anc;
if (hson[u])
dfs2(hson[u], anc);
for (re int i = head[u]; i; i = e[i].nxt)
if (e[i].v != fa[u] && e[i].v != hson[u])
dfs2(e[i].v, e[i].v);
}
inline int getlca(int u, int v)
{
while (top[u] != top[v])
{
if (dep[top[u]] < dep[top[v]])
swap(u, v);
u = fa[top[u]];
}
return dep[u] < dep[v] ? u : v;
}
inline int getdis(int u, int v)
{
int t = getlca(u, v);
return dep[u] + dep[v] - (dep[t] << 1);
}
} A, B;
int n, x, y, vis[N];
inline void bfs()
{
queue<int> Q;
vis[x] = 1, Q.push(x);
while (!Q.empty())
{
int u = Q.front();
Q.pop();
for (re int i = A.head[u]; i; i = A.e[i].nxt)
{
int v = A.e[i].v;
if (vis[v])
continue;
if (A.dep[v] < B.dep[v])
vis[v] = 1, Q.push(v);
}
}
}
int main()
{
n = read(), x = read(), y = read();
for (re int i = 1; i < n; ++i)
{
int u = read(), v = read();
A.addEdge(u, v), A.addEdge(v, u);
}
for (re int i = 1; i < n; ++i)
{
int u = read(), v = read();
B.addEdge(u, v), B.addEdge(v, u);
}
A.dfs1(x, 0), A.dfs2(x, x);
B.dfs1(y, 0), B.dfs2(y, y);
bfs();
int ans = 0;
for (re int u = 1; u <= n; ++u)
{
if (!vis[u])
continue;
for (re int i = A.head[u]; i; i = A.e[i].nxt)
{
int v = A.e[i].v;
if (B.getdis(u, v) > 2)
{
puts("-1");
return 0;
}
}
ans = max(ans, B.dep[u] - 1);
}
printf("%d\n", ans << 1);
return 0;
}
Submission Info
Submission Time 2020-01-20 11:49:15
Task E - Sugigma: The Showdown
User M_sea
Language C++14 (GCC 5.4.1)
Score 1400
Code Size 2389 Byte
Status AC
Exec Time 116 ms
Memory 68864 KB
评论
发表评论