20220510 noi7
tot: 235 (300)
rk: 2/28
简单题
100pts
做法很多
- 使用 ODT 维护区间覆盖，线段树维护区间加，ODT 变化时更新线段树上相应位置的贡献。常数较大
- 倒序。那么区间覆盖就变成了区间查询并清空
- 懒标记
考场代码
const int N = 5e5+5;
int n,m,q,a[N];
LL b[N];
#define ls (u<<1)
#define rs (u<<1|1)
struct { int l,r,p; LL add; } t[N*4];
void down_add(int u,LL x) {
if( ~t[u].p ) b[t[u].p] += x * (t[u].r-t[u].l+1);
else t[u].add += x;
}
void down(int u) {
if( t[u].add ) down_add(ls,t[u].add), down_add(rs,t[u].add), t[u].add = 0;
if( ~t[u].p ) t[ls].p = t[rs].p = t[u].p, t[u].p = -1;
}
void bld(int u=1,int l=1,int r=n) {
t[u].l = l, t[u].r = r, t[u].p = -1;
if( l == r ) return io>>t[u].p, void();
int mid = l+r>>1; bld(ls,l,mid), bld(rs,mid+1,r);
}
void cov(int ql,int qr,int x,int u=1) {
if( qr < t[u].l || t[u].r < ql ) return;
if( ql <= t[u].l && t[u].r <= qr ) return t[u].p = x, void();
down(u), cov(ql,qr,x,ls), cov(ql,qr,x,rs);
}
void add(int ql,int qr,int x,int u=1) {
if( qr < t[u].l || t[u].r < ql ) return;
if( ql <= t[u].l && t[u].r <= qr ) return down_add(u,x);
down(u), add(ql,qr,x,ls), add(ql,qr,x,rs);
}
void dfs(int u=1) {
if( t[u].l == t[u].r ) return;
down(u), dfs(ls), dfs(rs);
}
signed main() { freopen("easy.in","r",stdin); freopen("easy.out","w",stdout);
io>>n>>m>>q;
bld();
while( q-- ) {
int op,l,r,x; io>>op>>l>>r>>x;
op==1 ? cov(l,r,x) : add(l,r,x);
} dfs();
For(i,1,m) io<
树上游走
35pts, max = 100pts
极为复杂的树形 DP
以 \(s\) 为根，设 \(d[u]\) 为 \(u\) 的儿子个数，
- \(f[u]\) ：第一次走到 \(u\)，\(u\) 的子孙未被经过，\(fa[u]\) 已消失的期望。答案即为 \(f[s]\)
- \(g[u]\) ：第二次走到 \(u\)，\(u\) 的子孙未被经过，\(fa[u]\) 已消失的期望
- \(h[u]\) ：第一次走到 \(u\)，\(u\) 的子孙未被经过，\(fa[u]\) 仍存在但之后不经过 \(fa[u]\) 的期望（在子树 \(u\) 停止）。为了辅助转移，再记录 \(p[u]\) 表示这种情况下不经过 \(fa[u]\) 的概率
转移：
- \(f[u]\)：记 \(x\) 为第一个前往的儿子（概率 \(\frac{1}{d[u]}\)），有两种可能：
- 不再返回 \(u\)：贡献 \(h[x]\)
- 返回 \(u\)：
- 走到 \(x\)直接返回 \(u\)：贡献 \(\frac{1}{d[x]+1}(g[x]+\sum_{v\ne x}f[v])\)
- 向下走若干层再原路返回：若 \(d[u]=1\)，贡献 \((1-p[x]-\frac{1}{d[x]+1})val[u]\)；否则贡献 \((1-p[x]-\frac{1}{d[x]+1})\frac{1}{d[u]-1}\sum_{v\ne x}f[v]\)
- \(g[u]\) ：走到儿子 \(v\) 后 \(u\) 消失。贡献 \(\frac{1}{d[u]}f[v]\)
- \(h[u],p[u]\)：记 \(x\) 为第一个前往的儿子（概率 \(\frac{1}{d[u]+1}\)），有两种可能：
- 不再返回 \(u\)：贡献 \(h[x]\)，对 \(p[u]\) 贡献 \(p[x]\)
- 返回 \(u\)：
- 走到 \(x\) 直接返回 \(u\)：贡献 \(\frac{1}{(d[x]+1)(d[u]+1)}(g[x]+\sum_{v\ne x}f[v])\)，对 \(p[u]\) 贡献 \(\frac{d[u]}{(d[x]+1)(d[u]+1)}\)
- 向下走若干层再原路返回：贡献 \((1-p[x]-\frac{1}{d[x]+1})\frac{1}{d[u]}\sum_{v\ne x}f[v]\)（\(d[u]=1\) 时仍成立，因为只能走到 \(fa[u]\)，不合法，贡献 \(0\)），对 \(p[u]\) 贡献 \((1-p[x]-\frac{1}{d[x]+1})\frac{d[u]-1}{d[u]}\)
对于叶子：\(f[u]=g[u]=a[u],h[u]=p[u]=0\)
编一下思考过程：把 \(s\) 放到根比较自然，这样到 \(u\) 一定经过了 \(fa[u]\)。树形 DP 一般以子树划分阶段，本题体现为“走到 \(u\)，在子树 \(u\) 中结束”。影响接下来决策的只有 \(u,fa[u]\) 的经过次数，可以设出 \(f,g,h\)。转移考虑是否返回 \(u\) 、前往的儿子 \(x,v\)、\(x\) 的经过次数，需要用到“\(fa[u]\) 走到 \(u\) 再走到子树再走回 \(fa[u]\)”的概率，无法直接计算，额外维护出 \(p\) 辅助
code
const int N = 1e5+5;
int n,rt,d[N],a[N];
LL inv[N],f[N],g[N],h[N],p[N];
Vi e[N];
void dfs(int u,int fa) {
if( fa ) e[u].erase(find(all(e[u]),fa)); d[u] = sz(e[u]);
if( !d[u] ) return f[u] = g[u] = a[u], void();
LL ivd = inv[d[u]], ivd1 = inv[d[u]+1], sf = 0;
for(int v : e[u]) dfs(v,u), ckadd(sf,f[v]);
for(int v : e[u])
ckadd(f[u],h[v]),
(f[u] += inv[d[v]+1] * ivd %mod * (g[v]+sf-f[v])) %=mod,
(f[u] += (1-p[v]-inv[d[v]+1]) *
(d[u]==1 ? a[u] : (sf-f[v])*inv[d[u]-1]%mod)) %=mod;
(f[u] *= ivd) %=mod;
g[u] = sf * ivd %mod;
for(int v : e[u]) {
LL pp;
ckadd(h[u],h[v]), ckadd(p[u],p[v]);
pp = inv[d[v]+1] * ivd1 %mod,
(h[u] += pp * (g[v]+sf-f[v])) %=mod, (p[u] += pp * d[u]) %=mod;
pp = (1-p[v]-inv[d[v]+1]) * ivd %mod,
(h[u] += pp * (sf-f[v])) %=mod, (p[u] += pp * (d[u]-1)) %=mod;
}
(h[u] *= ivd1) %=mod, (p[u] *= ivd1) %=mod;
}
signed main() { freopen("walk.in","r",stdin); freopen("walk.out","w",stdout);
io>>n>>rt; For(i,1,n) io>>a[i];
Rep(i,1,n, x,y) io>>x>>y, e[x].pb(y), e[y].pb(x);
inv[0] = inv[1] = 1; For(i,2,n) inv[i] = (mod-mod/i) * inv[mod%i] %mod;
dfs(rt,0);
io<
树的同构
100pts
一个经典 trick 是枚举边，求 \(S,T\) 分属两侧的答案。考场直接默写 CF762F，时间复杂度 \(O(n^{3}2^{\lfloor\frac{n}{2}\rfloor})\)，可以被中心相连的两个菊花卡掉
注意到本题是求最大值（而那题是方案数），因此本题状压 DP 部分实际上是最大权匹配，可以做到 \(O(\text{poly }n)\)
顺便提一句：本题的较好的读入方式是读入至 EOF 共 \(2n-2\) 个数
考场代码
赛时重构过一半因此很丑
const int N = 55;
int n,ans,fr[N],to[N],rk[N],id[N],f[1<<25|4],g[N][N];
Vi e[N];
void input() {
string s; getline(cin,s);
for(stringstream sin(s); sin; sin>>fr[++n]);
Rep(i,1,n) cin>>to[i], ++fr[i], ++to[i];
}
struct Tree {
int n,m,fa[N]; bool vis[N];
void clr() { n = m = 0, mem(vis,0,::n); }
void dfs(int u,int f) { fa[u] = f; for(int v : e[u]) if( v != f ) dfs(v,u); }
} a,b;
void dfs(int u,int fa,Tree &x)
{ x.vis[u] = 1; for(int v : e[u]) if( v != fa ) dfs(v,u,x); }
void dp(int u) {
for(int v : e[u]) if( v != a.fa[u] ) dp(v);
For(i,1,n) if( b.vis[i] ) {
int m = 0; for(int j : e[i]) if( j != b.fa[i] ) id[m++] = j;
int U = (1<>j & 1) )
ckmax(f[s|1<