$n\leq 58$不是什么奇淫技巧，只是保证答案不会太大。
根据进入每一个点的次数等于离开该点的次数可以列出类似以下的方程组（对于$1$号点和最后到达的点，两者差值是定值）
$$x_i = \sum_{R_j=i} \lfloor \frac{x_j}{2} \rfloor + \sum_{B_j=i} \lceil \frac{x_j}{2} \rceil$$
（一共有$n$个这样的方程，其中$x_i$是离开点$i$的次数）
对于每一个点，输入给定的是离开该点次数的奇偶性，于是
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define ll long long int #define eps 1e-6 inline double _abs(double a){return a>0?a:-a;} int n,q,R[60],B[60]; int pos; char col[60]; struct matrix{ int mod,mat[60][120],f[60]; inline int sum(int a,int b){return a+b<mod?a+b:a+b-mod;} inline int dec(int a,int b){return a<b?a-b+mod:a-b;} inline int mul(int a,int b){return (int)((ll)a*b%mod);} inline int pow(int a,int b) { int res=1; while(b>0){ if(b&1) res=mul(res,a); a=mul(a,a); b>>=1; } return res; } inline int inv(int x){return pow(x,mod-2);} void gauss(void) { int half=inv(2); for(int i=0;i<n;i++){ mat[B[i]][i]=sum(mat[B[i]][i],half); mat[R[i]][i]=sum(mat[R[i]][i],half); mat[i][i]=dec(mat[i][i],1); } for(int i=0;i<n;i++) mat[i][i+n]=1; for(int i=0;i<n;i++){ int maxp=i; for(int j=i+1;j<n;j++) if(mat[j][i]>0) maxp=j; for(int j=0;j<n+n;j++) swap(mat[i][j],mat[maxp][j]); for(int j=0;j<n;j++) if(i!=j){ int t=mul(mat[j][i],inv(mat[i][i])); for(int k=0;k<n+n;k++) mat[j][k]=dec(mat[j][k],mul(mat[i][k],t)); } } for(int i=0;i<n;i++) for(int j=0;j<n;j++) mat[i][j+n]=mul(mat[i][j+n],inv(mat[i][i])); return; } void getf(void) { for(int i=0;i<n;i++) f[i]=0; int half=inv(2); for(int i=0;i<n;i++) if(col[i]==‘R‘){ f[R[i]]=sum(f[R[i]],half); f[B[i]]=dec(f[B[i]],half); } f[0]=sum(f[0],1); f[pos]=dec(f[pos],1); return; } int getout(int id) { int res=0; for(int i=0;i<n;i++) res=dec(res,mul(mat[id][i+n],f[i])); return res; } }m1,m2; struct edges{ int to; ll cnt; }e1[60],e2[60]; bool incyc[60],vis[60]; int sta[60],top=-1; inline ll query(int id) { return e1[id].cnt==0?e2[id].cnt:e1[id].cnt; } inline void dec(int id,ll x) { if(e1[id].cnt>=x){ e1[id].cnt-=x; return; } e2[id].cnt-=x-e1[id].cnt; e1[id].cnt=0; return; } bool check(void) { int now=0; while(e1[now].cnt+e2[now].cnt>0){ while(e1[now].cnt+e2[now].cnt>0&&!vis[now]){ vis[now]=1; sta[++top]=now; if(e1[now].cnt>0) now=e1[now].to; else now=e2[now].to; } if(!vis[now]) break; while(sta[top]!=now){ vis[sta[top]]=0; incyc[sta[top--]]=1; } vis[now]=0; incyc[now]=1; top--; ll mn=1e18; for(int i=0;i<n;i++) if(mn>query(i)&&incyc[i]) mn=query(i); for(int i=0;i<n;i++) if(incyc[i]){ dec(i,mn); incyc[i]=0; } } while(top>=0) dec(sta[top--],1); for(int i=0;i<n;i++) if(e1[i].cnt+e2[i].cnt!=0) return 0; return 1; } ll out[60]; ll getans(void) { m1.getf(); m2.getf(); for(int i=0;i<n;i++){ int p1=m1.getout(i),p2=m2.getout(i); ll k1=m1.mul(p1,m1.inv(m2.mod)); ll k2=m2.mul(p2,m2.inv(m1.mod)); k1*=m2.mod; k2*=m1.mod; out[i]=(k1+k2)%((ll)m1.mod*m2.mod); if((out[i]&1)&&col[i]==‘B‘) return -1; if(!(out[i]&1)&&col[i]==‘R‘) return -1; } for(int i=0;i<n;i++){ incyc[i]=vis[i]=0; if(out[i]&1ll){ e1[i].cnt=out[i]>>1ll; e1[i].to=B[i]; e2[i].cnt=(out[i]+1)>>1ll; e2[i].to=R[i]; } else{ e1[i].cnt=e2[i].cnt=out[i]>>1ll; e1[i].to=R[i]; e2[i].to=B[i]; } } if(!check()) return -1; ll ans=0; for(int i=0;i<n;i++) ans+=out[i]; return ans; } int main(void) { scanf("%d",&n); n--; for(int i=0;i<n;i++){ scanf("%d%d",&B[i],&R[i]); B[i]--; R[i]--; } m1.mod=1000000007; m2.mod=1000000009; m1.gauss(); m2.gauss(); scanf("%d",&q); while(q--){ scanf("%d",&pos); pos--; for(int i=0;i<n;i++) scanf(" %c",&col[i]); printf("%lld\n",getans()); } return 0; } /* */
原文：https://www.cnblogs.com/2005lz/p/14332476.html
