考场
乍一看都不好做
仔细想想发现 T1 的绝对值特别好，轮流选剩余的最大/最小值就行了
T2 又要计数，直接想部分分，发现一个 sb 容斥就有 35ps（但数据锅了，只有 25pts）
T3 什么玩意，发现线段树不会操作 6（线段树分裂啊，昨天刚打了板子），LCT 不会操作 2
，但 sub3（只维护黑点） 4（线段树维护序列） 都会
T4 高消直接死了，一分都没有。两个 sub 都是链，什么情况（考场上把 \(1\) 看成 \(i\)了）
迅速写+拍完前两题
想了想 T4 的系数递推，但列出的式子很不可做；貌似也不能高消一次求出所有答案，puts 样例了
感觉 T3 是比较擅长的题型，又想了很久，sub2 也会了（确定联通块后线段树），但直到 10.20 才开始写，最终只写完了 sub1 4
res
rk3 100+28+25+0（显示的是 rk4,因为出榜时 T3 在 judging。。。）
rk1 张王美誉 100+11+60+0
rk2 牛宏昊 100+44+10+0
rk4 付文暄 90+11+10+20（显示的是 rk3 的氪金玩家）
总结
想的太浅了，很多地方就差一点，还是要多思考，不要用写代码的勤奋掩盖思维的懒惰。
T3 正解就是在 sub3 的基础上加了个树剖、线段树，T4 给了菊花，sub3 的做法很明显（不过看错题也没啥好说的）
sol
T1
模拟。考场代码：
const int N = 3e5+5;
int n;
LL a[N];
LL ans,pre[N],suf[N];
signed main() {
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
read(n);
For(i,1,n) read(a[i]); sort(a+1,a+n+1);
For(i,1,n) pre[i] = pre[i-1] + a[i];
rFor(i,n,1) suf[i] = suf[i+1] + a[i];
for(int i = 1, l = 0, r = n+1; i <= n; ++i) {
if( i & 1 ) {
++l;
ans += (a[l] * (l-1) - pre[l-1]) + (suf[r] - a[l] * (n-r+1));
} else {
--r;
ans += (a[r] * l - pre[l]) + (suf[r+1] - a[r] * (n-r));
}
write(ans);
}
return iocl();
}
T2
发现暴力容斥时边集具体是什么并不重要，只要知道有多少条边即可。考虑树形 DP，设 \(f[u,i,0/1/2/3]\) 为子树 \(u\) 选 \(i\) 条边不合法，点 \(u\) 不选/选入边/选出边/都选的方案数。（显然一个点不能同时使两条入边/出边不合法）
const int N = 5e3+5, mod = 998244353;
int n,mm=1,head[N],to[N*2],w[N*2],nxt[N*2];
int siz[N];
LL ans,fac[N],f[N][N][4],g[N][4];
void dfs(int u,int fa) {
siz[u] = 1, f[u][0][0] = 1;
for(int e = head[u], v; v = to[e], e; e = nxt[e]) if( v != fa ) {
dfs(v,u);
memset(g,0,sizeof g);
For(i,0,siz[u]) For(j,0,siz[v]) {
LL fv = (f[v][j][0]+f[v][j][1]+f[v][j][2]+f[v][j][3]) %mod;
For(k,0,3) g[i+j][k] += f[u][i][k] * fv %mod;
if( w[e] )
g[i+j+1][2] += f[u][i][0] * (f[v][j][0]+f[v][j][2]) %mod,
g[i+j+1][3] += f[u][i][1] * (f[v][j][0]+f[v][j][2]) %mod;
else
g[i+j+1][1] += f[u][i][0] * (f[v][j][0]+f[v][j][1]) %mod,
g[i+j+1][3] += f[u][i][2] * (f[v][j][0]+f[v][j][1]) %mod;
}
siz[u] += siz[v];
For(i,1,siz[u]) For(j,0,3) f[u][i][j] = g[i][j] %mod;
}
}
signed main() {
read(n);
fac[0] = 1; For(i,1,n) fac[i] = fac[i-1] * i %mod;
For(i,1,n-1) {
int x,y; read(x,y);
to[++mm] = y, w[mm] = 1, nxt[mm] = head[x], head[x] = mm;
to[++mm] = x, w[mm] = 0, nxt[mm] = head[y], head[y] = mm;
}
dfs(1,0);
For(i,0,n-1)
ans += (i+1&1?1:-1) * fac[n-i] * (f[1][i][0]+f[1][i][1]+f[1][i][2]+f[1][i][3]) %mod;
write((ans%mod+mod)%mod);
return iocl();
}
T3
好题，需要很多 DS 技巧
发现每个白点的权值并不重要，只要知道它归属的黑点即可（可以树剖+set 单 \(\log\) 维护）。线段树维护每个黑点的权值和管辖点数，BIT 辅助
细节较多。
typedef unsigned U;
const int N = 3e5+5;
int n,m,fa[N];
int ind,dep[N],siz[N],son[N],top[N],dfn[N],rdfn[N];
VI to[N];
set<int> s[N];
void dfs1(int u) {
dep[u] = dep[fa[u]]+1, siz[u] = 1;
for(int v : to[u]) {
dfs1(v);
siz[u] += siz[v];
if( siz[v] > siz[son[u]] ) son[u] = v;
}
}
void dfs2(int u,int t) {
top[u] = t, dfn[u] = ++ind, rdfn[ind] = u;
if( son[u] ) dfs2(son[u],t);
for(int v : to[u]) if( v != son[u] ) dfs2(v,v);
}
int belong(int u) {
for(int v; v = top[u]; u = fa[top[u]])
if( !s[v].empty() && *s[v].begin() <= dep[u] ) {
auto it = s[v].upper_bound(dep[u]);
return rdfn[dfn[u]-(dep[u]-*--it)];
}
}
struct BIT {
U t1[N],t2[N];
void add(int i,U x) { for(int j=i;j<=n;j+=j&-j) t1[j] += x, t2[j] += i*x; }
U sum(int i)
{ U res=0; for(int j=i;j;j-=j&-j) res += (i+1)*t1[j]-t2[j]; return res; }
void modify(int l,int r,U x) { add(l,x), add(r+1,-x); }
U query(int l,int r) { return sum(r) - sum(l-1); }
} bit;
#define ls (u<<1)
#define rs (u<<1|1)
struct Node { int l,r; U siz,val,sum,add; } t[N*4];
void up(int u) {
t[u].siz = t[ls].siz + t[rs].siz,
t[u].val = t[ls].val + t[rs].val,
t[u].sum = t[ls].sum + t[rs].sum;
}
void down(int u,U x) { t[u].val += x, t[u].sum += t[u].siz*x, t[u].add += x; }
void down(int u) { down(ls,t[u].add), down(rs,t[u].add), t[u].add = 0; }
void build(int u,int l,int r) {
t[u].l = l, t[u].r = r;
if( l == r ) return;
int mid = l+r>>1;
build(ls,l,mid), build(rs,mid+1,r);
}
void addsiz(int u,int p,U x) {
if( t[u].l == t[u].r ) return t[u].siz += x, t[u].sum += x*t[u].val, void();
down(u);
addsiz( p<=t[ls].r?ls:rs ,p,x);
up(u);
}
void addval(int u,int l,int r,U x) {
if( l <= t[u].l && t[u].r <= r ) return down(u,x);
down(u);
if( l <= t[ls].r ) addval(ls,l,r,x);
if( t[rs].l <= r ) addval(rs,l,r,x);
up(u);
}
void covval(int u,int p,U x) {
if( t[u].l == t[u].r ) return t[u].val = x, t[u].sum = x*t[u].siz, void();
down(u);
covval( p<=t[ls].r?ls:rs ,p,x);
up(u);
}
U qsiz(int u,int l,int r) {
if( l > r ) return 0;
if( l <= t[u].l && t[u].r <= r ) return t[u].siz;
down(u);
U res = 0;
if( l <= t[ls].r ) res = qsiz(ls,l,r);
if( t[rs].l <= r ) res += qsiz(rs,l,r);
return res;
}
U qval(int u,int p) {
if( t[u].l == t[u].r ) return t[u].val;
down(u);
return qval( p<=t[ls].r?ls:rs ,p);
}
U qsum(int u,int l,int r) {
if( l > r ) return 0;
if( l <= t[u].l && t[u].r <= r ) return t[u].sum;
down(u);
U res = 0;
if( l <= t[ls].r ) res = qsum(ls,l,r);
if( t[rs].l <= r ) res += qsum(rs,l,r);
return res;
}
#undef ls
#undef rs
signed main() {
read(n,m);
For(i,2,n) read(fa[i]), to[fa[i]].pb(i);
dfs1(1), dfs2(1,1), build(1,1,n);
s[1].insert(1), addsiz(1,1,n);
while( m-- ) {
int op,u,v,l,r; U x,sizu; read(op,u); l = dfn[u], r = dfn[u]+siz[u]-1;
switch(op) {
case 1: write(qval(1,dfn[belong(u)])+bit.query(l,l)); break;
case 2: read(x); addval(1,l,l,x); break;
case 3:
write(qval(1,dfn[belong(u)])*(siz[u]-qsiz(1,l+1,r)) +
qsum(1,l+1,r) + bit.query(l,r));
break;
case 4: read(x); addval(1,l,r,x); break;
case 5:
v = belong(u), s[top[u]].insert(dep[u]);
sizu = siz[u]-qsiz(1,l+1,r);
covval(1,l,qval(1,dfn[v])), addsiz(1,l,sizu);
addsiz(1,dfn[v],-sizu);
break;
default:
v = belong(fa[u]), s[top[u]].erase(dep[u]);
sizu = siz[u]-qsiz(1,l+1,r);
U valu = qval(1,l), valv = qval(1,dfn[v]);
covval(1,l,0), addsiz(1,l,-sizu);
addsiz(1,dfn[v],sizu);
bit.modify(l,r,valu-valv), addval(1,l,r,-(valu-valv));
}
}
return iocl();
}
T4
先鸽了