이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC diagnostic ignored "-Wunused-parameter"
#pragma GCC diagnostic ignored "-Wunused-variable"
#pragma GCC diagnostic ignored "-Wparentheses"
#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
#define random random_device rd; mt19937 rng(rd())
using namespace std;
template<typename T1, typename T2>
ostream& operator << (ostream &i, pair<T1, T2> j) {
return i << j.first << ' ' << j.second;
}
template<typename T>
ostream& operator << (ostream &i, vector<T> j) {
i << '{' << j.size() << ':';
for (T ii : j) i << ' ' << ii;
return i << '}';
}
void Debug(bool _split) {}
template<typename T1, typename ...T2>
void Debug(bool _split, T1 x, T2 ...args) {
if (_split)
cerr << ", ";
cerr << x, Debug(true, args...);
}
template<typename T>
void Debuga(T *i, int n) {
cerr << '[';
for (int j = 0; j < n; ++j) cerr << i[j] << " ]"[j == n - 1];
cerr << endl;
}
#ifdef SYL
#define debug(args...) cerr << "\u001b[35mLine(" << __LINE__ << ") -> [" << #args << "] is [", Debug(false, args), cerr << "]\u001b[0m" << endl
#define debuga(i) cerr << "\u001b[35mLine(" << __LINE__ << ") -> [" << #i << "] is ", Debuga(i, sizeof(i) / sizeof(typeid(*i).name())), cerr << "\u001b[0m"
#else
#define debug(args...) void(0)
#define debuga(i) void(0)
#endif
typedef long long ll;
typedef pair<int, int> pi;
const int inf = 0x3f3f3f3f, lg = 20;
const ll mod = 1e9 + 7, INF = 0x3f3f3f3f3f3f3f3f;
vector<vector<int>> g, dp, pa;
vector<int> c, d, dep;
int n, s, t;
void dfs1(int i, int p, int _d) {
pa[i][0] = p, dep[i] = i == s ? 0 : dep[p] + 1;
if (i == t)
return c[i] = _d, d[i] = 0, void();
c[i] = _d + g[i].size() - (i != s);
for (int j : g[i])
if (j != p)
dfs1(j, i, c[i]);
}
int lca(int i, int j) {
if (dep[i] < dep[j])
swap(i, j);
for (int x = lg - 1; ~x; --x)
if (dep[pa[i][x]] >= dep[j])
i = pa[i][x];
for (int x = lg - 1; ~x; --x)
if (pa[i][x] != pa[j][x])
i = pa[i][x], j = pa[j][x];
return i == j ? i : pa[i][0];
}
void build() {
for (int i = 1; i < lg; ++i)
for (int j = 0; j < n; ++j)
pa[j][i] = pa[pa[j][i - 1]][i - 1];
for (int i = 0; i < n; ++i)
if (~dep[i]) {
int x = lca(i, t);
d[i] = c[i] + c[pa[t][0]] - c[x] - (x != s ? c[pa[x][0]] : 0) - dep[t] + dep[x];
}
}
bool dfs2(int i, int p) {
if (i == t)
return fill(all(dp[i]), d[i]), true;
vector<vector<int>> v(n + 1);
int ch = -1;
for (int j : g[i])
if (j != p) {
if (dfs2(j, i)) {
ch = j;
continue;
}
for (int x = 0; x <= n; ++x)
v[x].push_back(dp[j][x]);
}
for (int j = 0; j <= n; ++j)
sort(all(v[j]), [](int x, int y) {return x > y;});
int sz = v[0].size();
for (int j = 0; j <= n; ++j) {
dp[i][j] = inf;
for (int x = 0; x <= j; ++x) {
if (j - x + 1 > n || x > sz)
continue;
if (x == sz) {
if (~ch)
dp[i][j] = min(dp[i][j], x + dp[ch][j - x + 1]);
else
dp[i][j] = min(dp[i][j], d[i]);
break;
}
if (~ch)
dp[i][j] = min(dp[i][j], max(x + dp[ch][j - x + 1], v[j - x + 1][x]));
else
dp[i][j] = min(dp[i][j], v[j - x + 1][x]);
}
}
return ch != -1;
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> t >> s;
if (s == t)
return cout << 0, 0;
--s, --t;
g.resize(n), dp.assign(n, vector<int>(n + 1));
d.resize(n), dep.assign(n, -1), c.resize(n), pa.assign(n, vector<int>(lg));
for (int i = 0; i < n - 1; ++i) {
int x, y;
cin >> x >> y;
--x, --y;
g[x].push_back(y), g[y].push_back(x);
}
dfs1(s, s, 0);
build();
dfs2(s, -1);
cout << dp[s][1];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |