QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#722388#9713. Kill the treeNanani#TL 0ms0kbC++171.5kb2024-11-07 18:49:342024-11-07 18:49:35

Judging History

This is the latest submission verdict.

  • [2024-11-07 18:49:35]
  • Judged
  • Verdict: TL
  • Time: 0ms
  • Memory: 0kb
  • [2024-11-07 18:49:34]
  • Submitted

answer

//by 72
#include<bits/stdc++.h>
#define F(i, a, b) for(int i = a; i <= b; i ++)
#define Fd(i, a, b) for(int i = a; i >= b; i --)
#define pb push_back
#define pii pair<int, int>
#define fi first
#define se second
#define int long long
using namespace std;

const int mod = 998244353;
const int N = 2e5 + 10;
const int inf = 1e18;
typedef array<int, 3> a3; 
typedef long long ll;

int n, m, sz[N], dfn[N], rk[N], mx[N];
vector<int> ed[N];
int idx = 0;
void dfs(int u, int f) {
    sz[u] = 1;
    dfn[u] = ++ idx, rk[idx] = u;
    for(auto v : ed[u]) {
        if(v == f) continue;
        dfs(v, u);
        sz[u] += sz[v];
        mx[u] = max(sz[v], mx[u]);
    }
}
vector<int> res[N];
void dfs2(int u, int f) {
    for(auto v : ed[u]) {
        if(v == f) continue;
        dfs2(v, u);
    }
    vector<int> now;
    int mn = inf;
    F(i, dfn[u], dfn[u] + sz[u] - 1) {
        int v = rk[i];
        int tmp = max(mx[v], sz[u] - sz[v]);
        if(tmp == mn) now.push_back(v);
        else if(tmp < mn) now.clear(), mn = tmp, now.push_back(v);
    }
    res[u] = now;
}

void sol() {
    cin >> n;
    F(i, 1, n - 1) {
        int u, v; cin >> u >> v;
        ed[u].push_back(v), ed[v].push_back(u);
    }
    dfs(1, 1);
    dfs2(1, 1);
    F(i, 1, n) {
        sort(res[i].begin(), res[i].end());
        for(auto x : res[i]) cout << x << " "; cout << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    F(i, 1, t) sol();
    return 0;
}
//sldl

详细

Test #1:

score: 0
Time Limit Exceeded

input:

200000
42924 18271
60536 154257
107175 95680
196335 71607
158051 155259
110869 30974
143595 43516
4228 138046
26249 183847
123888 199873
15009 25362
166527 175160
15257 67159
124779 199363
148904 54047
5988 18123
58281 40739
44562 143880
72819 132492
137782 29662
130741 78276
55073 93292
82700 18328...

output:


result: