#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
#define sz(x) (int)x.size()
/*
Date: 2022/08/22 17:18
Problem Link: link
Topic(s):
Time Spent:
Solution Notes:
Root the tree at node t, where the mouse should end up.
For every subtree on the path from t to m, calculate the amount of time it takes for Dumbo to get the mouse down and
up the subtree. Meaning we would have to clean edges eventually to get the mouse back up the subtree.
We can do this using a dp: dp[u] = second max of dp[v] + # of children, where v is a children of u.
Now, we have to determine the order that we want to block these subtrees. We have to consider both the level these subtrees
are on and their dp value. We can imagine this as the "urgency" of a subtree. A subtree is more urgent if it is closer to the
mouse (or just that the mouse can reach it if you don't block it) and has higher dp value.
For example, if the mouse if on a node of depth 3, and it has 2 children of dp value == 2. The next level above has a node
without any children. Two levels above is a node with three children, of dp values 5, 6, 7 for example. Here, the most
urgent node is the one with dp value == 7, then 6, 5, and then 2. Meaning although the dp value 2 subtrees are closer to the
mouse right now, we want to the subtrees higher up with larger dp values first. If for any step we don't block off a subtree
on the node that's two levels up (the one with subtrees 5, 6, 7), the mouse can get into one of those subtrees, which has higher
value than 2, which is beneficial for the mouse.
However, if there were only two nodes of values 7 and 6 on that node two levels above, we are allowed to block off one of the
dp == 2 subtrees. So as you can see, there can be a lot of factors determining which subtree to block.
Essientially, the problems becomes how do we minimize the max dp value of the subtree that the mouse can go to.
When hearing this "minimize the max", we should think about binary search.
Let's binary search on the max dp value that we would allow the mouse to enter, i.e. we block every subtree with higher
value. Then, if the mouse is able to get into such a subtree, then we increase the max value, otherwise decrease it.
*/
const int MAXN = 1e6+5, INF = 1e9;
int n, t, m, par[MAXN], dep[MAXN], dp[MAXN], deg[MAXN];
vector<int> arr[MAXN];
bool onPath[MAXN];
void dfs(int at, int p, int d = 0){
par[at] = p;
dep[at] = d;
for (int u : arr[at]){
if (u != p){
dfs(u, at, d+1);
deg[at]++;
}
}
}
void dfs2(int at, int p){
int mx = 0, mx2 = 0;
for (int u : arr[at]){
if (u != p){
dfs2(u, at);
if (dp[u] >= mx){
mx2 = mx;
mx = dp[u];
}else if (dp[u] > mx2){
mx2 = dp[u];
}
}
}
dp[at] = mx2 + deg[at];
}
bool check(int x, vector<int>& path){
int sumdeg = 0;
for (int i : path){
sumdeg += deg[i];
}
if (sumdeg > x){
return false;
}
int cur = 0, need = 0;
for (int i : path){
cur++;
int reach = 0;
for (int u : arr[i]){
if (onPath[u]){
continue;
}
reach += (dp[u] + sumdeg) <= x;
need += (dp[u] + sumdeg) > x;
}
sumdeg -= reach;
if (need > cur){
return false;
}
}
return true;
}
int main(){
cin.tie(0); ios_base::sync_with_stdio(0);
// freopen("file.in", "r", stdin);
// freopen("file.out", "w", stdout);
cin >> n >> t >> m;
t--; m--;
for (int i=0; i<n-1; i++){
int a, b;
cin >> a >> b;
a--; b--;
arr[a].push_back(b);
arr[b].push_back(a);
}
dfs(t, -1);
vector<int> path;
int cur = m;
while (cur != t){
path.push_back(cur);
onPath[cur] = true;
cur = par[cur];
}
path.push_back(t);
for (int i=0; i<sz(path)-1; i++){
deg[i]--;
}
onPath[t] = true;
for (int i=0; i<sz(path)-1; i++){
for (int u : arr[path[i]]){
if (!onPath[u]){
dfs2(u, path[i]);
}
}
}
int low = 0, high = INF;
while (low < high){
int mid = (low + high)/2;
if (check(mid, path)){
high = mid;
}else{
low = mid+1;
}
}
cout << low << "\n";
}
/**
* Debugging checklist:
* - Reset everything after each TC
* - Integer overflow, index overflow
* - Special cases?
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
303 ms |
82068 KB |
Output is correct |
| 2 |
Correct |
255 ms |
76300 KB |
Output is correct |
| 3 |
Correct |
785 ms |
85100 KB |
Output is correct |
| 4 |
Correct |
404 ms |
54276 KB |
Output is correct |
| 5 |
Correct |
765 ms |
85128 KB |
Output is correct |
| 6 |
Correct |
807 ms |
85036 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
