2026-05-13 22:40:53
发布于：浙江
23阅读
0回复
0点赞
#include <bits/stdc++.h>
#define BUFSIZE 10000000
struct read {
char buf[BUFSIZE], *p1, *p2, c;
read(): p1(buf), p2(buf) {}
char gc(void) {
return p1 == p2 && (p2 = buf + fread(p1 = buf, 1, BUFSIZE, stdin), p1 == p2) ? EOF : *p1++;
}
read &operator >>(unsigned &x) {
for (c = gc(), x = 0; c < '0' || c > '9'; c = gc());
for (; c >= '0' && c <= '9'; c = gc())
x = x * 10 + (c - '0');
return *this;
}
} cin;
struct write {
char buf[BUFSIZE], *p1, *p2;
write(): p1(buf), p2(buf + BUFSIZE) {}
~write() {
fwrite(buf, 1, p1 - buf, stdout);
}
void pc(char c) {
p1 == p2 &&(fwrite(buf, 1, p1 - buf, stdout), p1 = buf), *p1++ = c;
}
write &operator <<(long long x) {
static unsigned stk[30], tp;
do stk[tp++] = '0' + x % 10, x /= 10;
while (x);
while (tp)
pc(stk[--tp]);
return *this;
}
write &operator <<(char c) {
return pc(c), *this;
}
} cout;
unsigned n, s[500010][2], fail[500010];
unsigned val[500010], a[500010], p[500010];
namespace TT {
unsigned rt, cnt, sz[1000010], csz[1000010], A[1000010], B[1000010], ls[500010], rs[500010], tp[500010];
unsigned s[500010], fa[500010], son[500010];
unsigned newnode(unsigned x) {
unsigned u = x + n;
csz[u] = sz[u] = 1, A[u] = B[u] = x;
return u;
}
unsigned bd(unsigned x, unsigned y, unsigned p) {
unsigned u = ++cnt;
ls[u] = x, rs[u] = y, sz[u] = sz[x] + sz[y], tp[u] = p;
if (p == 0)
csz[u] = csz[x] + csz[y], A[u] = A[x], B[u] = B[y];
else
csz[u] = csz[x], A[u] = A[x], B[u] = B[x];
return u;
}
unsigned c[500010], cs[500010], ccnt;
unsigned cbuild(unsigned l, unsigned r, unsigned p) {
if (l == r)
return c[l];
unsigned u = std::lower_bound(cs + l, cs + r, cs[l - 1] + (cs[r] - cs[l - 1]) / 2) - cs;
if (u == r)
return bd(cbuild(l, r - 1, p), c[r], p);
else
return bd(cbuild(l, u, p), cbuild(u + 1, r, p), p);
}
unsigned build(unsigned x) {
unsigned u = x;
static unsigned tmp[500010];
while (u) {
for (auto w : ::s[u])
if (w && w != son[u])
tmp[w] = build(w);
ccnt = 0, c[++ccnt] = newnode(u), cs[ccnt] = 1;
for (auto w : ::s[u])
if (w && w != son[u])
c[++ccnt] = tmp[w], cs[ccnt] = cs[ccnt - 1] + sz[tmp[w]];
tmp[u] = cbuild(1, ccnt, 1), u = son[u];
}
u = x, ccnt = 0;
while (u)
c[++ccnt] = tmp[u], cs[ccnt] = cs[ccnt - 1] + sz[tmp[u]], u = son[u];
return cbuild(1, ccnt, 0);
}
unsigned R[1000010], ct;
void ini(unsigned x) {
if (x > n)
return A[x] = B[x] = R[x] = ++ct, void();
ini(ls[x]), ini(rs[x]);
A[x] = A[A[x] + n], B[x] = B[B[x] + n];
R[x] = ct;
}
void dfs(unsigned x) {
static unsigned pt, f[500010];
f[pt++] = x, s[x] = 1, son[x] = 0;
if (a[x] >= pt)
p[x] = 0;
else
p[x] = f[a[x]];
for (unsigned u : ::s[x])
if (u)
fa[u] = x, dfs(u), s[x] += s[u], son[x] = (s[son[x]] > s[u] ? son[x] : u);
--pt;
}
void init() {
cnt = 0;
dfs(1);
rt = build(1);
ini(rt);
}
}
std::vector<unsigned> vec[500010];
unsigned sz[500010];
void dfs(unsigned x) {
sz[x] = 1;
for (auto u : vec[x])
dfs(u), sz[x] += sz[u];
}
long long ans[500010];
#define MAXN 2100010
unsigned cct, ls[MAXN], rs[MAXN], mn[MAXN], lmn[MAXN], cnt[MAXN], tag[MAXN];
long long sum[MAXN], stk[MAXN], tp;
inline unsigned newnode(unsigned pos) {
using TT::csz;
unsigned u = tp ? stk[--tp] : ++cct;
ls[u] = rs[u] = 0, tag[u] = sum[u] = mn[u] = 0, cnt[u] = csz[pos], lmn[u] = 2e9;
return u;
}
inline void addtag(unsigned x, unsigned v) {
sum[x] += 1ll * (v - mn[x]) * cnt[x];
mn[x] = tag[x] = v;
}
inline void pushdown(unsigned x, unsigned pos) {
if (!tag[x])
return;
if (!ls[x])
ls[x] = newnode(TT::ls[pos]);
if (TT::tp[pos] == 0) {
if (!rs[x])
rs[x] = newnode(TT::rs[pos]);
if (mn[ls[x]] == mn[rs[x]])
addtag(ls[x], tag[x]), addtag(rs[x], tag[x]);
else if (mn[ls[x]] < mn[rs[x]])
addtag(ls[x], tag[x]);
else
addtag(rs[x], tag[x]);
} else
addtag(ls[x], tag[x]);
tag[x] = 0;
}
inline void pushup(unsigned x, unsigned pos) {
using TT::csz;
if (TT::tp[pos] == 0) {
if (!ls[x] && !rs[x])
sum[x] = mn[x] = 0, cnt[x] = csz[pos], lmn[x] = 2e9;
else if (!ls[x])
sum[x] = sum[rs[x]], mn[x] = 0, lmn[x] = (mn[rs[x]] == 0 ? lmn[rs[x]] : mn[rs[x]]),
cnt[x] = csz[TT::ls[pos]] + (mn[rs[x]] == 0 ? cnt[rs[x]] : 0);
else if (!rs[x])
sum[x] = sum[ls[x]], mn[x] = 0, lmn[x] = (mn[ls[x]] == 0 ? lmn[ls[x]] : mn[ls[x]]),
cnt[x] = csz[TT::rs[pos]] + (mn[ls[x]] == 0 ? cnt[ls[x]] : 0);
else {
if (mn[ls[x]] == mn[rs[x]])
sum[x] = sum[ls[x]] + sum[rs[x]], mn[x] = mn[ls[x]], lmn[x] = std::min(lmn[ls[x]], lmn[rs[x]]),
cnt[x] = cnt[ls[x]] + cnt[rs[x]];
else if (mn[ls[x]] < mn[rs[x]])
sum[x] = sum[ls[x]] + sum[rs[x]], mn[x] = mn[ls[x]], lmn[x] = std::min(lmn[ls[x]], mn[rs[x]]),
cnt[x] = cnt[ls[x]];
else
sum[x] = sum[ls[x]] + sum[rs[x]], mn[x] = mn[rs[x]], lmn[x] = std::min(mn[ls[x]], lmn[rs[x]]),
cnt[x] = cnt[rs[x]];
}
} else if (!ls[x])
sum[x] = mn[x] = 0, cnt[x] = csz[pos], lmn[x] = 2e9;
else
sum[x] = sum[ls[x]], mn[x] = mn[ls[x]], cnt[x] = cnt[ls[x]], lmn[x] = lmn[ls[x]];
}
inline void beats(unsigned &rt, unsigned v, unsigned pos) {
if (!rt)
rt = newnode(pos);
if (v <= mn[rt])
return;
if (v < lmn[rt])
return addtag(rt, v);
tag[rt] = 0;
beats(ls[rt], v, TT::ls[pos]), beats(rs[rt], v, TT::rs[pos]);
pushup(rt, pos);
}
inline void lupdate(unsigned b, unsigned v, unsigned &rt, unsigned pos = TT::rt) {
using TT::B, TT::R;
if (!rt)
rt = newnode(pos);
if (B[pos] == b)
return beats(rt, v, pos);
pushdown(rt, pos);
if (b <= R[TT::ls[pos]])
lupdate(b, v, ls[rt], TT::ls[pos]);
else
beats(ls[rt], v, TT::ls[pos]), lupdate(b, v, rs[rt], TT::rs[pos]);
pushup(rt, pos);
}
inline void rupdate(unsigned a, unsigned v, unsigned &rt, unsigned pos = TT::rt) {
using TT::A, TT::R;
if (!rt)
rt = newnode(pos);
if (A[pos] == a)
return beats(rt, v, pos);
pushdown(rt, pos);
if (a > R[TT::ls[pos]])
rupdate(a, v, rs[rt], TT::rs[pos]);
else
rupdate(a, v, ls[rt], TT::ls[pos]), beats(rs[rt], v, TT::rs[pos]);
pushup(rt, pos);
}
inline void update(unsigned a, unsigned b, unsigned v, unsigned &rt, unsigned pos = TT::rt) {
using TT::A, TT::B, TT::R;
if (!rt)
rt = newnode(pos);
if (A[pos] == a && B[pos] == b)
return beats(rt, v, pos);
pushdown(rt, pos);
if (b <= R[TT::ls[pos]])
update(a, b, v, ls[rt], TT::ls[pos]);
else if (a > R[TT::ls[pos]])
update(a, b, v, rs[rt], TT::rs[pos]);
else
rupdate(a, v, ls[rt], TT::ls[pos]), lupdate(b, v, rs[rt], TT::rs[pos]);
pushup(rt, pos);
}
inline long long query(unsigned b, unsigned rt, unsigned pos = TT::rt) {
using TT::B, TT::R;
if (!rt)
return 0;
if (B[pos] == b)
return sum[rt];
pushdown(rt, pos);
if (b <= R[TT::ls[pos]])
return query(b, ls[rt], TT::ls[pos]);
else
return sum[ls[rt]] + query(b, rs[rt], TT::rs[pos]);
}
void merge(unsigned &x, unsigned y, unsigned pos = TT::rt) {
using TT::A, TT::B;
if (!x || !y)
return x |= y, void();
if (pos > n)
return sum[x] = mn[x] = std::max(mn[x], mn[y]), stk[tp++] = y, void();
unsigned u = std::max(tag[x], tag[y]);
tag[x] = 0;
merge(ls[x], ls[y], TT::ls[pos]);
merge(rs[x], rs[y], TT::rs[pos]);
pushup(x, pos);
if (u)
beats(x, u, pos);
stk[tp++] = y;
}
unsigned solve(unsigned x) {
unsigned rt = 0;
std::sort(vec[x].begin(), vec[x].end(), [&](unsigned x, unsigned y) {
return sz[x] > sz[y];
});
for (auto u : vec[x])
merge(rt, solve(u));
if (p[x])
update(TT::A[p[x] + n], TT::A[x + n], val[x], rt);
ans[x] = query(TT::A[x + n], rt);
return rt;
}
void solve() {
cin >> n;
for (unsigned i = 1; i <= n; i++)
s[i][0] = s[i][1] = fail[i] = 0, vec[i].clear(), vec[i].shrink_to_fit();
for (unsigned i = 2, x, v; i <= n; i++)
cin >> x >> v, s[x][v] = i;
for (unsigned i = 1; i <= n; i++)
cin >> val[i];
for (unsigned i = 1; i <= n; i++)
cin >> a[i];
TT::init();
static unsigned que[500010];
unsigned *hd = que, *tl = que;
for (unsigned i = 0; i < 2; i++)
if (s[1][i])
*tl++ = s[1][i], fail[s[1][i]] = 1;
else
s[1][i] = 1;
while (hd != tl) {
unsigned p = *hd++;
for (unsigned i = 0; i < 2; i++)
if (s[p][i])
fail[s[p][i]] = s[fail[p]][i], *tl++ = s[p][i];
else
s[p][i] = s[fail[p]][i];
}
for (unsigned i = 2; i <= n; i++)
vec[fail[i]].push_back(i);
dfs(1);
cct = tp = 0, lmn[0] = 2e9;
solve(1);
for (unsigned i = 1; i <= n; i++)
cout << ans[i] << ' ';
cout << '\n';
}
int main() {
int a[10000000];
unsigned T;
cin >> T;
while (T--)
solve();
return 0;
}
全部评论 1
#include <iostream> #include <algorithm> #include <vector> #define int long long #define BUFSIZE 10000000 struct read { char buf[BUFSIZE], *p1, *p2, c; read(): p1(buf), p2(buf) {} char gc(void) { return p1 == p2 && (p2 = buf + fread(p1 = buf, 1, BUFSIZE, stdin), p1 == p2) ? EOF : *p1++; } read &operator >>(unsigned &x) { for (c = gc(), x = 0; c < '0' || c > '9'; c = gc()); for (; c >= '0' && c <= '9'; c = gc()) x = x * 10 + (c - '0'); return *this; } } cin; struct write { char buf[BUFSIZE], *p1, *p2; write(): p1(buf), p2(buf + BUFSIZE) {} ~write() { fwrite(buf, 1, p1 - buf, stdout); } void pc(char c) { p1 == p2 &&(fwrite(buf, 1, p1 - buf, stdout), p1 = buf), *p1++ = c; } write &operator <<(long long x) { static unsigned stk[30], tp; do stk[tp++] = '0' + x % 10, x /= 10; while (x); while (tp) pc(stk[--tp]); return *this; } write &operator <<(char c) { return pc(c), *this; } } cout; unsigned n, s[500010][2], fail[500010]; unsigned val[500010], a[500010], p[500010]; namespace TT { unsigned rt, cnt, sz[1000010], csz[1000010], A[1000010], B[1000010], ls[500010], rs[500010], tp[500010]; unsigned s[500010], fa[500010], son[500010]; unsigned newnode(unsigned x) { unsigned u = x + n; csz[u] = sz[u] = 1, A[u] = B[u] = x; return u; } unsigned bd(unsigned x, unsigned y, unsigned p) { unsigned u = ++cnt; ls[u] = x, rs[u] = y, sz[u] = sz[x] + sz[y], tp[u] = p; if (p == 0) csz[u] = csz[x] + csz[y], A[u] = A[x], B[u] = B[y]; else csz[u] = csz[x], A[u] = A[x], B[u] = B[x]; return u; } unsigned c[500010], cs[500010], ccnt; unsigned cbuild(unsigned l, unsigned r, unsigned p) { if (l == r) return c[l]; unsigned u = std::lower_bound(cs + l, cs + r, cs[l - 1] + (cs[r] - cs[l - 1]) / 2) - cs; if (u == r)1周前 来自 浙江
0
有帮助，赞一个