#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
const ll NMAX = 200002;
const ll INF = (1LL << 60);
const ll nrbits = 20;
const ll MOD = 998244353;
const ll bucket = 320;
const double eps = 0.00000001;
vector <int> banned, stiva;
vector <int> v[NMAX];
map <int, int> mp[NMAX];
int ban[NMAX], b, a;
int dp[NMAX];
int pa[NMAX];
int vechi[NMAX];
void DFS(int node, int p){
pa[node] = p;
if(node == b){
banned = stiva;
for(auto x : stiva){
ban[x] = 1;
}
}
if(node != a)
stiva.push_back(node);
for(auto x : v[node]){
if(x == p) continue;
DFS(x, node);
}
if(node != a)
stiva.pop_back();
}
int calculeaza(int node){
if(mp[node].size() == 0) return 0;
pii x = *prev(mp[node].end());
return x.first + x.second;
}
void DFS1(int node, int p){
vector <int> s;
for(auto x : v[node]){
if(x == p) continue;
DFS1(x, node);
if(ban[x] == 0 && x != a && x != b)
mp[node][dp[x]]++;
}
dp[node] = vechi[node] = calculeaza(node);
}
void sterge(int a, int b){
mp[a][b]--;
if(mp[a][b] == 0){
mp[a].erase(b);
}
}
int f(int unde){
int ultim = -1;
if(unde != -1){
ultim = banned[unde];
}
for(int i = unde - 1; i >= 0; i--){
int x = banned[i + 1];
int node = banned[i];
mp[node][dp[x]]++;
dp[node] = calculeaza(node);
ultim = node;
}
if(ultim != -1){
mp[b][dp[ultim]]++;
dp[b] = calculeaza(b);
}
int sol = dp[b];
if(ultim != -1){
sterge(b, dp[ultim]);
dp[b] = calculeaza(b);
}
for(int i = 0; i < unde; i++){
int x = banned[i + 1];
int node = banned[i];
sterge(node, dp[x]);
dp[node] = calculeaza(node);
}
ultim = -1;
if(unde + 1 != banned.size()){
ultim = banned[unde + 1];
}
for(int i = unde + 2; i < banned.size(); i++){
int x = banned[i - 1];
int node = banned[i];
mp[node][dp[x]]++;
dp[node] = calculeaza(node);
ultim = node;
}
if(ultim != -1){
mp[a][dp[ultim]]++;
dp[a] = calculeaza(a);
}
sol = max(sol, dp[a]);
if(ultim != -1){
sterge(a, dp[ultim]);
dp[a] = calculeaza(a);
}
for(int i = banned.size() - 1; i >= unde + 2; i--){
int x = banned[i - 1];
int node = banned[i];
sterge(node, dp[x]);
dp[node] = calculeaza(node);
}
return sol;
}
int ternary(int st, int dr){
if(st + 1 >= dr){
return min(f(st), f(dr));
}
int mid = st + (dr - st) / 3;
int mid1 = dr - (dr - st) / 3;
if(f(mid) > f(mid1)){
return ternary(mid + 1, dr);
}
return ternary(st, mid1 - 1);
}
signed main() {
#ifdef HOME
ifstream cin(".in");
ofstream cout(".out");
#endif // HOME
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, i;
cin >> n >> a >> b;
for(i = 1; i < n; i++){
int x, y;
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
DFS(a, 0);
DFS1(a, 0);
int minim = 2e9;
for(i = (-1) + 1; i < banned.size() + 1; i++){
minim = min(minim, f(i - 1));
}
cout << minim;
return 0;
}
Compilation message
torrent.cpp: In function 'int f(int)':
torrent.cpp:96:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | if(unde + 1 != banned.size()){
| ~~~~~~~~~^~~~~~~~~~~~~~~~
torrent.cpp:99:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(int i = unde + 2; i < banned.size(); i++){
| ~~^~~~~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:155:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
155 | for(i = (-1) + 1; i < banned.size() + 1; i++){
| ~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
17496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
54 ms |
44160 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
