QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#140779#5157. High-quality TreeAs3b_team_f_masr#RE 0ms0kbC++142.2kb2023-08-16 20:12:452023-08-16 20:12:47

Judging History

你现在查看的是最新测评结果

  • [2023-08-16 20:12:47]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-08-16 20:12:45]
  • 提交

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

output:


result: