20251223NOI模拟赛
T2.灯泡控制
题面：
\(n\) 个灯泡摆成一圈，每个有状态开关，初始都是关闭。每次进行操作：
-
如果一个关闭的灯泡相邻位置有点亮的，则点亮它，对所有灯泡同时进行。
-
随机一个位置点亮，如果本来就是亮的则无事发生。
求点亮所有灯泡的期望操作轮数。 \(n\leq 10000\)
题解：
发现操作灯泡变量的个数和具体位置无关，和连续段有关，所以考虑连续段 DP。
对于环上连续段，由于开头结尾相邻，合并连续段时，连续段之间的前后位置关系不好处理，容易算重。有技巧之记录的连续段 \(A,B\) 是无序的，直到 \(A,B\) 合成为 \(C\) 时再决定 \(C=A+B\) 或 \(C=B+A\)。这样就不用管环的问题。
将操作分为三步：向左扩展，向右扩展，随机点亮。
记 \(f_{i,j},g_{i,j}\) 分别表示当前点亮 \(i\) 盏灯，形成 \(j\) 个连续段的期望和概率。
考虑扩展操作：
预处理 \(w_{i,j}\) 表示将 \(i\) 个段合成 \(j\) 个段的方案数。
-
转移考虑最后一个段自成一段 \(w_{i-1,j-1}\to w_{i,j}\)。
-
或者考虑最后一个段合成到前面某个段。如果它合成到一个由原来的 \(a\) 个段合并成的新段中，考虑此时决定相对位置有 \(a+1\) 种情况，所以一共有 \(i-1+j\) 种情况。即 \(w_{i-1,j}\times (i-1+j)\to w_{i,j}\)。
考虑随机点亮操作：
-
点亮自成一段 \((i-1,j-1)\to(i,j)\)。
-
延长一段 \((i-1,j)\times 2j\to(i,j)\)。
-
合并一段 \((i-1,j+1)\times j(j+1)\to(i,j)\)。注意因为段在合并前无序，所以排列数随意选择两个合并。
-
无事发生 \((i,j)\times i\to(i,j)\)。
注意由于是环所以点亮前的最后一步操作要枚举。
连续段个数不超过 \(\sqrt n\)，所以复杂度 \(O(n^2)\)
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;inline int read(){int s=0,k=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-') k=-1;c=getchar();}while(c>='0'&&c<='9'){s=(s<<3)+(s<<1)+(c^48);c=getchar();}return s*k;
}const int N=1e4+5,M=105,mod=998244353;
int n,m;
ll f[3][N][M],g[3][N][M],w[M][M],inc;ll Mod(ll x){return x>=mod?x-mod:x;}
void Add(ll &x,ll y){x=Mod(x+y);}ll ksm(ll a,ll b){ll t=1;for(;b;b>>=1,a=a*a%mod)if(b&1) t=t*a%mod;return t;
}int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);n=read();m=sqrt(n);if(n==1){puts("1");return 0;}inc=ksm(n,mod-2);w[0][0]=1;for(int i=1;i<=m;i++)for(int j=1;j<=i;j++)w[i][j]=(w[i-1][j-1]+w[i-1][j]*(i+j-1))%mod;f[0][1][1]=1;g[0][1][1]=1;for(int i=2;i<=n;i++){for(int o=1;o<=2;o++)for(int j=1;j<=i&&j<=m;j++) for(int k=j;k<i&&k<=m;k++){(f[o][i][j]+=f[o-1][i-k][k]*w[k][j])%=mod;(g[o][i][j]+=g[o-1][i-k][k]*w[k][j])%=mod;}for(int j=1;j<=i&&j<=m;j++){(f[0][i][j]+=f[2][i-1][j-1]+f[2][i-1][j]*2*j+f[2][i-1][j+1]*j*(j+1)+f[2][i][j]*i)%=mod;(g[0][i][j]+=g[2][i-1][j-1]+g[2][i-1][j]*2*j+g[2][i-1][j+1]*j*(j+1)+g[2][i][j]*i)%=mod;(f[0][i][j]*=inc)%=mod;(g[0][i][j]*=inc)%=mod;Add(f[0][i][j],g[0][i][j]);}}ll ans=0;(ans+=Mod(f[2][n-1][1]+g[2][n-1][1])*inc)%=mod;w[0][1]=1;for(int i=1;i<=m;i++)(ans+=(f[0][n-i][i]+f[1][n-i][i]+g[0][n-i][i]+g[1][n-i][i])%mod*w[i-1][1]%mod)%=mod;printf("%lld",ans);return 0;
}
T3.树上的数
题面：
给定一个 \(n\) 个点的树，初始每个点有点权 \(a_i\)。每次操作你可以选择一个节点 \(x\)，将 \(a_x\) 赋值为其邻域点权和减 \(a_x\)，并将其邻域点权全部赋为 \(0\)。执行任意次操作后使得最终只剩下一个非 \(0\) 点时求这个点的最大值。\(n\leq 10^6,-10^9\leq a_i\leq 10^9\)
题解：
每个点对最终答案贡献系数为 \(1\) 或 \(-1\)。
设初始未合并的点为 \(A\) 类点，涉及过合并操作的点为 \(B\) 类点。
发现 \(B\) 类点可以任意更改正负，且可以在其经过的路径上任意搬运。
进一步的，当场上存在 \(A\) 类点时，每次合并操作最多涉及一个 \(B\) 类点，直到都是 \(B\) 类点时，由于上述性质，答案为所有 \(B\) 类点绝对值之和。任意操作方案都可以转化为这样的操作方案一定不劣。
结论是问题可以转化为：将树的若干边割断变成森林，对于森林中每个树选择一个根，要求任意两棵树的根在原树上不相邻。还要求每棵树以选择点为根时，兄弟节点贡献系数相同，根节点与其儿子系数不同。
对于一个操作方案，直到所有点都是 \(B\) 类点之前的合并过程中，将其合并操作不涉及到的所有边切割，得到一个森林，显然一个森林始终有一个 \(B\) 类点。将其第一次操作的位置作为根，两根不能相邻。由根不断向外扩展吸收 \(A\) 类点，每次所有兄弟会一起被合并，所以兄弟节点系数相同。
对于一个切割方案，如果一个切割边两边都不是根那显然可以做到两边互不影响，否则如果有一边是根则必须先合并另一边才能操作这个根。对于所有有一边是根的两个连通块之间连一条有向边，根据拓扑序操作每个联通块，可以达到最终效果。
考虑树形 DP，对每个 \(x\) 记录状态：
-
其到父亲的边被切割，且该节点不是根节点，子树内的最大贡献
-
其到父亲的边被切割，且该节点是根节点，子树内的最大贡献；
-
其到父亲的边未被切割，且根节点在子树外，子树内（自身除外）的最大贡献；
-
其到父亲的边未被切割，且根节点在子树内，子树内以及父亲节点的最大贡献；
转移时考虑枚举本层兄弟节点那个相同的系数是 \(1/-1\)，考虑根的位置（父亲，子树，自己）转移即可。复杂度 \(O(n)\)。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;inline ll read(){ll s=0,k=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-') k=-1;c=getchar();}while(c>='0'&&c<='9'){s=(s<<3)+(s<<1)+(c^48);c=getchar();}return s*k;
}void write(ll x){if(x>=10) write(x/10);putchar('0'+x%10);
}const int N=1e6+5;
const ll inf=1e18+7;
int n,fat[N];
ll a[N],f[N][4];
vector<int>e[N];void dfs(int x){if(e[x].size()==0){f[x][0]=-inf;f[x][1]=llabs(a[x]);f[x][2]=0;f[x][3]=llabs(a[x]-a[fat[x]]);return ;}for(int v:e[x]) dfs(v);ll sum[2]={0,0},mx[2]={-inf,-inf};for(int v:e[x]){ll val;val=max(a[v]+f[v][2],max(f[v][0],f[v][1]));sum[0]+=val; mx[0]=max(mx[0],f[v][3]-val);val=max(-a[v]+f[v][2],max(f[v][0],f[v][1]));sum[1]+=val; mx[1]=max(mx[1],f[v][3]-val);}f[x][0]=max(sum[0]+mx[0],sum[1]+mx[1]);f[x][2]=max(sum[0],sum[1]);f[x][3]=max(sum[0]+mx[0]+a[fat[x]],sum[1]+mx[1]-a[fat[x]]);sum[0]=sum[1]=0;for(int v:e[x]){sum[0]+=max(a[v]+f[v][2],f[v][0]);sum[1]+=max(-a[v]+f[v][2],f[v][0]);}f[x][1]=max(sum[0]-a[x],sum[1]+a[x]);f[x][3]=max({f[x][3],sum[0]+a[fat[x]]-a[x],sum[1]-a[fat[x]]+a[x]});
}void solve(){n=read();for(int i=1;i<=n;i++) a[i]=read();for(int i=2;i<=n;i++){fat[i]=read();e[fat[i]].push_back(i);}dfs(1);write(max(f[1][0],f[1][1]));putchar('\n');for(int i=1;i<=n;i++) e[i].clear();
}int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);int ID=read(),T=read();while(T--) solve();return 0;
}