QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#722388 | #9713. Kill the tree | Nanani# | TL | 0ms | 0kb | C++17 | 1.5kb | 2024-11-07 18:49:34 | 2024-11-07 18:49:35 |
Judging History
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...