QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#895254 | #8518. Roars III | winsun | WA | 2ms | 26468kb | C++14 | 7.4kb | 2025-02-12 11:21:42 | 2025-02-12 11:21:44 |
Judging History
answer
#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <queue>
#include <map>
#include <tuple>
#define fi first
#define se second
#define eb emplace_back
#define ep emplace
using namespace std;
typedef long long LL;
template <typename Tp> void read(Tp& x) {
char ch; bool op = 0; x = 0;
do ch = getchar(), op |= ch == '-'; while (ch < '0' || ch > '9');
do x = (x<<3)+(x<<1)+(ch&15), ch = getchar(); while (ch >= '0' && ch <= '9');
if (op) x = -x;
}
int read01() {
char ch;
do ch = getchar(); while (ch != '0' && ch != '1');
return ch & 1;
}
const int mod = 998244353;
inline int fplus(int x, int y) { return x + y >= mod ? x + y - mod : x + y; }
inline int Fplus(int& x, int y) { return x = fplus(x, y); }
inline int fminus(int x, int y) { return x - y < 0 ? x - y + mod : x - y; }
inline int Fminus(int& x, int y) { return x = fminus(x, y); }
int qpow(int x, int y = mod - 2) {
int res = 1;
if (x >= mod) x %= mod;
for (; y; y >>= 1, x = 1ll * x * x % mod) if (y & 1) res = 1ll * res * x % mod;
return res;
}
const int MAXN = 2e5+5;
int n, c[MAXN], head[MAXN], ver[MAXN<<1], nxt[MAXN<<1], tot;
void add(int x, int y) {
ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
}
int pa[MAXN], dep[MAXN], siz[MAXN], hvy[MAXN];
void dfs1(int x) {
dep[x] = dep[pa[x]] + 1, siz[x] = 1, hvy[x] = 0;
for (int i = head[x]; i; i = nxt[i]) {
int y = ver[i];
if (y == pa[x]) continue;
pa[y] = x;
dfs1(y);
siz[x] += siz[y];
if (siz[y] > siz[hvy[x]]) hvy[x] = y;
}
}
int dfn[MAXN], idx[MAXN], top[MAXN], cnt;
void dfs2(int x) {
dfn[x] = ++cnt, idx[cnt] = x;
if (!top[x]) top[x] = x;
if (!hvy[x]) return;
top[hvy[x]] = top[x];
dfs2(hvy[x]);
for (int i = head[x]; i; i = nxt[i]) {
int y = ver[i];
if (y == pa[x] || y == hvy[x]) continue;
dfs2(y);
}
}
struct Node {
int cnt, mx;
LL sum;
Node(): cnt(0), mx(-1), sum(0) {}
Node(int x): cnt(1), mx(x), sum(x) {}
Node(int t, int x, LL s): cnt(t), mx(x), sum(s) {}
friend Node operator+(const Node& x, const Node& y) {
return Node(x.cnt+y.cnt, max(x.mx, y.mx), x.sum+y.sum);
}
void app(int x) {
if (~mx) mx += x, assert(~mx);
sum += (LL)cnt * x;
}
};
namespace SGT {
Node s[MAXN<<2]; int t[MAXN<<2];
#define mid ((l + r) >> 1)
void build(int x, int l, int r) {
if (l == r) {
int u = idx[l];
s[x] = c[u] ? Node(dep[u]) : Node();
return;
}
build(x<<1, l, mid), build(x<<1|1, mid+1, r);
s[x] = s[x<<1] + s[x<<1|1];
}
void addtag(int x, int l, int r, int v) {
s[x].app(v), t[x] += v;
if (l == r) dep[idx[l]] += v;
}
void spread(int x, int l, int r) {
if (!t[x]) return;
addtag(x<<1, l, mid, t[x]), addtag(x<<1|1, mid+1, r, t[x]);
t[x] = 0;
}
void update(int x, int l, int r, int p) {
if (l == r) {
int u = idx[l];
s[x] = c[u] ? Node(dep[u]) : Node();
return;
}
spread(x, l, r);
if (p <= mid) update(x<<1, l, mid, p);
else update(x<<1|1, mid+1, r, p);
s[x] = s[x<<1] + s[x<<1|1];
}
void add(int x, int l, int r, int L, int R, int v) {
if (L <= l && R >= r) return addtag(x, l, r, v);
spread(x, l, r);
if (L <= mid) add(x<<1, l, mid, L, R, v);
if (R > mid) add(x<<1|1, mid+1, r, L, R, v);
s[x] = s[x<<1] + s[x<<1|1];
}
int bins(int x, int l, int r) {
if (l == r) return idx[l];
spread(x, l, r);
if (s[x<<1].mx >= s[x<<1|1].mx) return bins(x<<1, l, mid);
else return bins(x<<1|1, mid+1, r);
}
void getseg(int x, int l, int r, int L, int R, vector<tuple<int, int, int> >& vec) {
if (L <= l && R >= r) return vec.eb(x, l, r), void();
spread(x, l, r);
if (L <= mid) getseg(x<<1, l, mid, L, R, vec);
if (R > mid) getseg(x<<1|1, mid+1, r, L, R, vec);
}
int vldmaxdep(int L, int R) {
vector<tuple<int, int, int> > vec;
getseg(1, 1, n, L, R, vec);
int x, l, r, mxx = 0, pl = -1, pr = -1;
for (auto tp : vec) {
tie(x, l, r) = tp;
// printf("x=%d, l=%d, r=%d %d\n", x, l, r, s[x].mx);
if (!mxx || (mxx && s[x].mx > s[mxx].mx)) mxx = x, pl = l, pr = r;
}
assert(mxx);
if (s[mxx].mx == -1) return -1;
return bins(mxx, pl, pr);
}
}
int pos[MAXN]; LL ans[MAXN];
void dfs3(int x) {
SGT::add(1, 1, n, 1, n, 1), SGT::add(1, 1, n, dfn[x], dfn[x]+siz[x]-1, -2);
ans[x] = SGT::s[1].sum;
for (int i = head[x]; i; i = nxt[i]) {
int y = ver[i];
if (y == pa[x]) continue;
dfs3(y);
}
SGT::add(1, 1, n, dfn[x], dfn[x]+siz[x]-1, 2), SGT::add(1, 1, n, 1, n, -1);
// printf("aft%d %lld %d\n", x, SGT::s[1].sum, SGT::s[1].cnt);
}
void dfs4(int x) {
for (int i = head[x]; i; i = nxt[i]) {
int y = ver[i];
if (y == pa[x]) continue;
dfs4(y);
}
if (c[x]) return pos[x] = x, void();
int y = SGT::vldmaxdep(dfn[x], dfn[x] + siz[x] - 1);
// printf("x=%d, y=%d\n", x, y);
if (~y) {
assert(c[y]);
pos[x] = y;
c[y] = 0, c[x] = 1;
SGT::update(1, 1, n, dfn[y]);
SGT::update(1, 1, n, dfn[x]);
}
}
void dfs5(int x) {
// printf("bef%d %lld %d\n", x, SGT::s[1].sum, SGT::s[1].cnt);
SGT::add(1, 1, n, 1, n, 1), SGT::add(1, 1, n, dfn[x], dfn[x]+siz[x]-1, -2);
int p;
if (pos[x] && pos[x] != x) {
assert(c[x]), assert(!c[pos[x]]);
c[pos[x]] = 1, SGT::update(1, 1, n, dfn[pos[x]]);
p = SGT::bins(1, 1, n);
c[p] = 0, SGT::update(1, 1, n, dfn[p]);
// printf("%d %d %d\n", x, pos[x], p);
} else if (!pos[x]) {
p = SGT::bins(1, 1, n);
c[p] = 0, c[x] = 1;
SGT::update(1, 1, n, dfn[p]), SGT::update(1, 1, n, dfn[x]);
}
ans[x] -= SGT::s[1].sum;
for (int i = head[x]; i; i = nxt[i]) {
int y = ver[i];
if (y == pa[x]) continue;
dfs5(y);
}
if (pos[x] && pos[x] != x) {
c[p] = 1, SGT::update(1, 1, n, dfn[p]);
c[pos[x]] = 0, SGT::update(1, 1, n, dfn[pos[x]]);
} else if (!pos[x]) {
c[p] = 1, c[x] = 0;
SGT::update(1, 1, n, dfn[p]), SGT::update(1, 1, n, dfn[x]);
}
SGT::add(1, 1, n, dfn[x], dfn[x]+siz[x]-1, 2), SGT::add(1, 1, n, 1, n, -1);
// printf("aft%d %lld %d\n", x, SGT::s[1].sum, SGT::s[1].cnt);
}
int main() {
#ifndef ONLINE_JUDGE
assert(freopen("qoj8518.in", "r", stdin));
assert(freopen("qoj8518.out", "w", stdout));
#endif
read(n);
for (int i = 1; i <= n; ++i) c[i] = read01();
for (int i = 1; i < n; ++i) {
int x, y; read(x), read(y); add(x, y), add(y, x);
}
dfs1(1), dfs2(1);
// for (int i = 1; i <= n; ++i) printf("%d%c", dep[i], " \n"[i==n]);
SGT::build(1, 1, n);
dfs3(1);
// for (int i = 1; i <= n; ++i) printf("%lld%c", ans[i], " \n"[i==n]);
dfs4(1);
// for (int i = 1; i <= n; ++i) printf("%d%c", c[i], " \n"[i==n]);
// for (int i = 1; i <= n; ++i) printf("%d%c", pos[i], " \n"[i==n]);
dfs5(1);
for (int i = 1; i <= n; ++i) printf("%lld%c", ans[i], " \n"[i==n]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 24428kb
input:
5 10101 1 2 2 3 2 4 4 5
output:
2 2 2 3 3
result:
ok 5 number(s): "2 2 2 3 3"
Test #2:
score: 0
Accepted
time: 1ms
memory: 22364kb
input:
1 0
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 0ms
memory: 24268kb
input:
1 1
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 0ms
memory: 26464kb
input:
2 10 1 2
output:
0 1
result:
ok 2 number(s): "0 1"
Test #5:
score: 0
Accepted
time: 1ms
memory: 26468kb
input:
3 100 2 3 2 1
output:
0 1 2
result:
ok 3 number(s): "0 1 2"
Test #6:
score: 0
Accepted
time: 2ms
memory: 26332kb
input:
4 1100 4 1 4 3 4 2
output:
1 1 3 1
result:
ok 4 number(s): "1 1 3 1"
Test #7:
score: 0
Accepted
time: 0ms
memory: 24416kb
input:
5 10100 4 5 1 3 2 1 3 5
output:
0 2 0 4 2
result:
ok 5 number(s): "0 2 0 4 2"
Test #8:
score: -100
Wrong Answer
time: 0ms
memory: 26464kb
input:
8 11001000 4 2 7 2 5 7 6 2 3 1 6 3 7 8
output:
5 1 5 4 3 3 3 6
result:
wrong answer 2nd numbers differ - expected: '3', found: '1'