A
初始时只有 \(a_k=1\)，有 \(m\) 次操作，每次交换 \(a_u,a_v\) 的值，问忽略多少次操作可以使最终 \(a_i=1\).
简单DP即可。
code
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=1e5+10,inf=2e9;
int n,m,k,a[N],b[N],dp[N];
int main() {
scanf("%d%d%d",&n,&k,&m);
for(int i=1; i<=m; i++) scanf("%d%d",&a[i],&b[i]);
if(m==0) {
for(int i=1; i<=n; i++)
if(i==k) printf("0 ");
else printf("-1 ");
return 0;
}
for(int i=1; i<=n; i++) dp[i]=inf;
dp[k]=0;
for(int i=1; i<=m; i++) {
int x=a[i],y=b[i];
if(x==y) continue;
int t=dp[x];
dp[x]=min(dp[x]+1,dp[y]);
dp[y]=min(dp[y]+1,t);
}
for(int i=1; i<=n; i++) printf("%d ",dp[i]>=inf?-1:dp[i]);
return 0;
}
B
问树的每条边分别删去（询问独立），剩下两个部分每个部分中连通块的数量。
换根DP即可。
原始方程，\(u\) 为子树根时: \(s_u=\prod (1+s_v)\)
换根方程，\(u\) 为总树根时：\(dp_u=s_u*(\dfrac{dp_f}{1+s_u}+1)\)
code
#include<algorithm>
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long LL;
const LL N=5e5+10,mod=998244353;
LL n,tot,head[N],ver[2*N],nxt[2*N],fu[N],fv[N];
LL s[N],depth[N],dp[N],sum[N];
void addedge(LL x,LL y) {
ver[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
void DFS(LL u,LL father) {
s[u]=1;
depth[u]=depth[father]+1;
for(LL i=head[u]; i; i=nxt[i]) {
LL v=ver[i];
if(v==father) continue;
DFS(v,u);
s[u]=s[u]*(1+s[v])%mod;
sum[u]+=sum[v];
}
sum[u]=(sum[u]+s[u])%mod;
}
LL exgcd(LL a,LL b,LL &x,LL &y) {
if(b==0) {x=1; y=0; return a;}
LL g=exgcd(b,a%b,x,y),z=x;
x=y; y=z-(a/b)*x;
return g;
}
LL f(LL a,LL b) {
LL d,y;
exgcd(b,mod,d,y);
return (a*d%mod+mod)%mod;
}
void dfs2(LL u,LL father) {
if(u!=1) dp[u]=s[u]*(f(dp[father],s[u]+1)+1)%mod;
else dp[u]=s[u];
for(LL i=head[u]; i; i=nxt[i]) {
LL v=ver[i];
if(v==father) continue;
dfs2(v,u);
}
}
signed main() {
freopen("cut.in","r",stdin);
freopen("cut.out","w",stdout);
scanf("%lld",&n);
for(LL i=1; i<n; i++) {
scanf("%lld%lld",&fu[i],&fv[i]);
addedge(fu[i],fv[i]);
addedge(fv[i],fu[i]);
}
DFS(1,1);
dfs2(1,1);
for(LL i=1; i<n; i++) {
LL u=fu[i],v=fv[i];
if(depth[u]>depth[v]) {
printf("%lld %lld\n",sum[u]%mod,(sum[1]-sum[u]-(dp[v]-f(dp[v],s[u]+1))+10000*mod)%mod);
} else {
printf("%lld %lld\n",(sum[1]-sum[v]-(dp[u]-f(dp[u],s[v]+1))+10000*mod)%mod,sum[v]%mod);
}
}
return 0;
}