#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44
/*
const int MOD = ;
inline void mod(int &x) {
if(x >= MOD)
x -= MOD;
}
inline void add(int &x, int y) {
x += y;
mod(x);
}
inline void sub(int &x, int y) {
x += MOD - y;
mod(x);
}
inline void mul(int &x, int y) {
x = (1LL * x * y) % MOD;
}
*/
using namespace std;
const ll INF = 1e18;
const int MAXN = (int) 3e5;
vector <int> g[MAXN + 1];
int deg[MAXN + 1];
bool leaf[MAXN + 1];
ll vals[MAXN + 1];
ll dp[MAXN + 1][2];
// dp[nod][0] = drumul max pe care te termini daca nu ai revenit in nod
// dp[nod][1] = drumul max pe care te termini daca revi in nod
void dfs(int nod, int par, int delta) {
int son = 0;
for(auto it : g[nod]) {
if(it != par && leaf[it] == 0) {
dfs(it, nod, delta);
son++;
}
}
dp[nod][0] = dp[nod][1] = -INF;
if(son == 0) {
dp[nod][0] = vals[nod] - delta;
dp[nod][1] = vals[nod] - 2 * delta;
return ;
}
vector <ll> aux(2);
aux[0] = vals[nod] - delta;
aux[1] = 0;
for(auto it : g[nod]) {
if(it == par || leaf[it]) {
continue;
}
vector <ll> cur(2, -INF);
cur[0] = max(aux[0], max(aux[0] + dp[it][1] - delta, aux[1] + dp[it][0]));
cur[1] = max(aux[1], aux[1] + dp[it][1] - delta);
swap(cur, aux);
}
aux[1] = max(aux[1] + vals[nod] - delta, vals[nod] - 2 * delta);
for(int i = 0; i < 2; i++) {
dp[nod][i] = aux[i];
}
}
inline ll check(int delta) {
dfs(1, 0, delta);
return max(dp[1][0], dp[1][1]);
}
int main() {
//ifstream cin("A.in");
//ofstream cout("A.out");
int i, n;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
for(i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
deg[x]++, deg[y]++;
}
for(i = 1; i <= n; i++) {
if(deg[i] == 1 && i != 1) {
leaf[i] = 1;
}
vals[i] = deg[i] - (i != 1);
}
int res = -1;
for(int step = 1 << 18; step; step >>= 1) {
if(check(res + step) > 0) {
res += step;
}
}
cout << res + 1;
//cin.close();
//cout.close();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
8 ms |
7424 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
8 ms |
7424 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
8 ms |
7424 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
9 ms |
7424 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
25 ms |
8192 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
63 ms |
9636 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
383 ms |
14752 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
866 ms |
22236 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1571 ms |
28636 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1477 ms |
28604 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |