QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#121334 | #4839. Smaller LCA | memset0 | WA | 5ms | 22056kb | C++20 | 6.6kb | 2023-07-07 23:12:45 | 2023-07-07 23:12:47 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 9;
int n, rt, all, tot, tim, fa[N], siz[N], mxp[N], dfn[N], ans[N];
bool vis[N];
vector<int> cur, G[N];
vector<tuple<int, int, int, int>> qry;
namespace ini {
int tot, fa[N], dfn[N], siz[N];
long long sum, pre[N];
void dfs(int u) {
dfn[u] = ++tot;
siz[u] = 1;
for (int v : G[u])
if (v != fa[u]) {
fa[v] = u;
dfs(v);
siz[u] += siz[v];
}
}
void push(int u, int x) {
pre[dfn[u]] += x;
pre[dfn[u] + 1] -= x;
}
void push(int u, int v, int x) {
if (v == fa[u]) {
pre[0] += x;
pre[dfn[u]] -= x;
pre[dfn[u] + siz[u]] += x;
} else {
pre[dfn[v]] += x;
pre[dfn[v] + siz[v]] -= x;
}
}
inline void push(int u, int v, int w, int x) {
// fprintf(stderr, "push %d %d %d : %d\n", u, v, w, x);
pre[0] += x;
push(u, v, -x);
// for (int i = 0; i <= n; i++) cerr << pre[i] << " \n"[i == n];
push(u, w, -x);
// for (int i = 0; i <= n; i++) cerr << pre[i] << " \n"[i == n];
}
void init() {
dfs(1);
// for (int i = 1; i <= n; i++) cerr << dfn[i] << " \n"[i == n];
// for (int i = 1; i <= n; i++) cerr << siz[i] << " \n"[i == n];
}
void solve() {
// for (int i = 0; i <= n; i++) cerr << pre[i] << " \n"[i == n];
for (int i = 1; i <= n; i++) pre[i] += pre[i - 1];
// for (int i = 0; i <= n; i++) cerr << pre[i] << " \n"[i == n];
for (int i = 1; i <= n; i++) ans[i] += pre[dfn[i]];
}
} // namespace ini
struct CountNode {
int n, tim, s[N << 1];
vector<int> ans, valx, valy;
vector<pair<int, int>> nod;
vector<tuple<int, int, int>> qry;
inline void add(int k) {
for (; k <= n; k += k & -k) s[k]++;
}
inline void ask(int k, int &x) {
for (; k; k -= k & -k) x += s[k];
}
inline void addNode(int x, int y) {
// cerr << "counter::addNode " << x << " " << y << endl;
nod.emplace_back(x, y);
valx.push_back(x), valy.push_back(y);
}
inline void addQuery(int x, int y) {
// cerr << "counter::addQuery " << x << " " << y << endl;
qry.emplace_back(x, y, qry.size());
valx.push_back(x), valy.push_back(y);
}
inline int getQuery() {
// cerr << "counter::getQuery " << ans[tim] << endl;
return ans[tim++];
}
void init() {
// cerr << "counter::init" << endl;
tim = 0, nod.clear(), qry.clear(), valx.clear(), valy.clear();
}
void solve() {
ans.resize(qry.size());
fill(ans.begin(), ans.end(), 0);
if (!nod.size() || !qry.size()) return;
if (nod.size() < 5) {
for (auto &[xx, yy] : nod) {
for (auto &[x, y, i] : qry) {
if (xx <= x && yy <= y) ans[i]++;
}
}
return;
}
cerr << "counter::solve " << nod.size() << " " << qry.size() << endl;
sort(valx.begin(), valx.end());
sort(valy.begin(), valy.end());
valx.erase(unique(valx.begin(), valx.end()), valx.end());
valy.erase(unique(valy.begin(), valy.end()), valy.end());
n = valy.size();
fill(s, s + n + 1, 0);
for (auto &[x, y] : nod) {
x = lower_bound(valx.begin(), valx.end(), x) - valx.begin() + 1;
y = lower_bound(valy.begin(), valy.end(), y) - valy.begin() + 1;
// cerr << "node " << x << " " << y << endl;
}
for (auto &[x, y, i] : qry) {
x = upper_bound(valx.begin(), valx.end(), x) - valx.begin();
y = upper_bound(valy.begin(), valy.end(), y) - valy.begin();
// cerr << "query " << x << " " << y << " " << i << endl;
}
sort(nod.begin(), nod.end());
sort(qry.begin(), qry.end());
int i = 0, j = 0;
for (int x = 1; x <= valx.size(); x++) {
while (i < nod.size() && nod[i].first == x) {
add(nod[i].second), i++;
}
while (j < qry.size() && get<0>(qry[j]) == x) {
ask(get<1>(qry[j]), ans[get<2>(qry[j])]), j++;
}
}
}
} counter;
void getroot(int u) {
siz[u] = 1, mxp[u] = 0;
for (int v : G[u])
if (!vis[v] && v != fa[u]) {
fa[v] = u;
getroot(v);
siz[u] += siz[v];
mxp[u] = max(mxp[u], siz[v]);
}
mxp[u] = max(mxp[u], all - siz[u]);
if (!rt || mxp[u] < mxp[rt]) rt = u;
}
void getnode(int u) {
// cerr << "get node " << u << endl;
cur.push_back(u);
dfn[u] = ++tot, siz[u] = 1;
for (int v : G[u]) {
if (!vis[v] && v != fa[u]) {
fa[v] = u;
getnode(v);
siz[u] += siz[v];
}
}
}
void getquery(int u) {
// cerr << "get query " << u << endl;
for (int v : G[u])
if (!vis[v] && v != fa[u]) {
counter.addQuery(dfn[v] + siz[v] - 1, u - 1);
counter.addQuery(dfn[v] - 1, u - 1);
getquery(v);
}
}
void pushans(int u) {
// cerr << "push ans " << u << " " << w << " " << tot << endl;
for (int v : G[u])
if (!vis[v] && v != fa[u]) {
int cur = counter.getQuery();
cur -= counter.getQuery();
ini::push(u, v, fa[u], cur);
pushans(v);
}
}
void solve(int u) {
// cerr << "=== solve " << u << " ===" << endl;
vis[u] = 1;
vector<int> ch;
set<pair<int, int>> pre = {{u, 0}};
tot = 1, dfn[u] = siz[u] = 1;
for (int v : G[u]) {
if (!vis[v]) ch.push_back(v);
}
for (int v : ch) {
fa[v] = u;
cur.clear(), getnode(v);
siz[u] += siz[v];
for (int x : cur)
for (auto &[y, w] : pre) {
if ((long long)x * y < n) {
counter.addNode(dfn[x], x * y);
if (w) counter.addNode(dfn[y], x * y);
if (u > (long long)x * y) {
ini::push(u, v, w, 1);
}
} else {
break;
}
}
for (int x : cur) pre.insert(make_pair(x, v));
}
qry.clear(), tim = 0;
counter.init();
for (int v : ch) getquery(v);
counter.solve();
for (int v : ch) pushans(v);
// cerr << tim << " " << qry.size() << endl;
for (int v : ch) {
rt = 0, all = siz[v], getroot(v);
// fprintf(stderr, "%d -> %d :: rt = %d, all = %d, mxp = %d\n", u, v, rt, all, mxp[rt]);
solve(rt);
}
}
int main() {
#ifdef memset0
// freopen("1.in", "r", stdin);
freopen("2.in", "r", stdin);
freopen("2.out", "w", stdout);
#endif
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for (int u, v, i = 1; i < n; i++) {
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
ini::init();
rt = 0, all = n, getroot(1), solve(rt);
ini::solve();
long long tot = (long long)n * (n - 1) / 2 + n;
// for (int i = 1; i <= n; i++) cerr << ans[i] << " \n"[i == n];
cerr << "time: " << clock() / (double)CLOCKS_PER_SEC << endl;
for (int i = 1; i <= n; i++) cout << (tot - ans[i]) << '\n';
cerr << "time: " << clock() / (double)CLOCKS_PER_SEC << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 5ms
memory: 22056kb
input:
5 1 2 4 2 2 5 3 5
output:
15 15 15 15 15
result:
wrong answer 5th numbers differ - expected: '14', found: '15'