QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#140779 | #5157. High-quality Tree | As3b_team_f_masr# | RE | 0ms | 0kb | C++14 | 2.2kb | 2023-08-16 20:12:45 | 2023-08-16 20:12:47 |
answer
#include <bits/stdc++.h>
typedef long double ld;
typedef long long ll;
using namespace std;
int di[] = {1, 0, -1, 0, 0, 1, -1, 1};
int dj[] = {0, 1, 0, -1, -1, 0, 1, -1};
const ll oo = 1e18, MOD = 1e9 + 7;
const int N = 3e5 + 5, M = 30005;
int t, n, m, ans;
int vis[N], timer , in[N], out[N], mx[N];
pair<int,int> dp[N];
vector<int> g[N];
set<int> lvls[N];
int solve(int s,int p,int lvl){
for(auto it:g[s]){
if(it != p){
solve(it,s,lvl+1);
if(abs(dp[s].first - dp[s].second) <= 1) continue;
int mx = max(dp[s].first , dp[s].second),mn = min(dp[s].first , dp[s].second);
{
int nlvl = mx - (mx - mn -1)+1;
auto it = lvls[nlvl].lower_bound(in[s]);
while (lvls[nlvl].end() != it){
it = lvls[nlvl].lower_bound(in[s]);
if(it != lvls[nlvl].end() && *it < out[s]){
lvls[nlvl].erase(it);
ans++;
} else
break;
}
while (1){
++nlvl;
if(lvls[nlvl].size()){
ans += lvls[nlvl].size();
lvls[nlvl].clear();
}else
break;
}
}
}
}
}
int dfs(int s,int p,int lvl){
in[s] = ++timer;
lvls[lvl].insert(in[s]);
int mx = lvl;
dp[s].second = lvl;
for(auto it:g[s]){
if(it != p){
auto tmp = dfs(it,s,lvl+1);
mx = max(mx,tmp);
if(!dp[s].first) {
dp[s] = {mx , dp[s].second};
}else{
dp[s] = {dp[s].first, mx };
}
}
}
out[s] = ++timer;
return mx;
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//freopen("output.txt", "w", stdout);
cin >> n;
for(int i = 1; i < n ;++i){
int u,v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,1,1);
solve(1,1,1);
cout << ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
6 1 2 1 3 3 4 3 5 5 6