分析
首先，每个点只能被修一次，代表它最多与两条铁路相连。
然后，发现答案不会太大，大概在$\log$级别。
于是设$f[i][j][k]\ (k\in\{0,1,2\})$表示以$i$为根的子树，答案为$j$，与$k$条铁路相连的方案数。
转移枚举子节点修还是不修即可，比较简单 。
最后答案怎么搞见代码。
还有，因为把未计算过的状态标为$0$，所以最好取膜后不要出现$0$，也就是让$Q$取膜后还是$Q$。
代码
//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=200000+10;
struct Edge { int v,nxt; };
Edge e[N<<1];
int head[N],cnt=0;
inline void addEdge(int u,int v) {
e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;
}
int n,m,Q,tot=0;
int f[N][20][3];
inline void dfs(int u,int fa) {
++tot;
for (re int i=0;i<20;++i) f[u][i][0]=1;
for (re int i=head[u];i;i=e[i].nxt) {
int v=e[i].v; if (v==fa) continue;
dfs(v,u);
for (re int j=0;j<20;++j) {
int A=0,B=0;
if (j) A=(1ll*f[v][j-1][0]+f[v][j-1][1]+f[v][j-1][2]-1)%Q+1;
B=(1ll*f[v][j][0]+f[v][j][1]-1)%Q+1;
f[u][j][2]=(1ll*f[u][j][2]*A+1ll*f[u][j][1]*B-1)%Q+1;
f[u][j][1]=(1ll*f[u][j][1]*A+1ll*f[u][j][0]*B-1)%Q+1;
f[u][j][0]=(1ll*f[u][j][0]*A-1)%Q+1;
}
}
}
int main() {
n=read(),m=read(),Q=read();
for (re int i=1;i<=m;++i) {
int u=read(),v=read();
addEdge(u,v),addEdge(v,u);
}
dfs(1,0); if (tot<n) { puts("-1\n-1"); return 0; }
int ans=0x3f3f3f3f,sum=0;
for (re int i=0;i<20;++i)
if (f[1][i][0]||f[1][i][1]||f[1][i][2]) { ans=i; break; }
sum=(1ll*f[1][ans][0]+f[1][ans][1]+f[1][ans][2])%Q;
printf("%d\n%d\n",ans,sum);
return 0;
}
怎么就Bzoj200AC了
%%%%%%%%%%
您又不把以前的题交上来qwq
交了也没200qwq
假死了 您可是LuoguAC900的神仙