发现就是傻逼论文题，或者今年九省联考的希望看了题解也就知道这道题怎么容斥了
具体方法是考虑 点 数 = 边 数 − 1 点数=边数-1 点数=边数−1
直接统计每个 G G G的答案减去所有边两侧都是 G G G的答案就完了
#include<bits/stdc++.h> using namespace std; #define gc getchar inline int read(){ char ch=gc(); int res=0,f=1; while(!isdigit(ch))f^=ch=='-',ch=gc(); while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc(); return f?res:-res; } const int mod=1e9+7; const int N=2005; struct edge{ int u,v,w; }e[N]; inline int add(int a,int b){ return a+b>=mod?a+b-mod:a+b; } inline void Add(int &a,int b){ a=add(a,b); } inline int dec(int a,int b){ return a-b<0?a-b+mod:a-b; } inline void Dec(int &a,int b){ a=dec(a,b); } inline int mul(int a,int b){ return 1ll*a*b>=mod?1ll*a*b%mod:a*b; } inline void Mul(int &a,int b){ a=mul(a,b); } int adj[N],nxt[N<<1],to[N<<1],val[N<<1],cnt,ans,col[N],lim,n,pb[N],pt[N]; inline void addedge(int u,int v,int w){ nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v,val[cnt]=w; } char op[N]; void dfs(int u,int fa,int dep){ if(dep>lim){pt[u]=pb[u]=0;return;} pt[u]=(col[u]!=3),pb[u]=(col[u]!=1); for(int e=adj[u];e;e=nxt[e]){ int v=to[e]; if(v==fa)continue; dfs(v,u,dep+val[e]); Mul(pt[u],pt[v]+1),Mul(pb[u],pb[v]+1); } } inline void calc(int u){ dfs(u,0,0); Add(ans,mul(pb[u],pt[u])); } inline void calc(int u,int v,int w){ dfs(u,v,w),dfs(v,u,w); Dec(ans,mul(mul(pt[u],pb[u]),mul(pt[v],pb[v]))); } int main(){ n=read(),lim=read(); scanf("%s",op+1); for(int i=1;i<=n;i++){ if(op[i]=='R')col[i]=1; if(op[i]=='G')col[i]=2; if(op[i]=='B')col[i]=3; } for(int i=1;i<n;i++){ int u=read(),v=read(),w=read(); e[i].u=u,e[i].v=v,e[i].w=w; addedge(u,v,w),addedge(v,u,w); } for(int i=1;i<=n;i++)if(col[i]==2)calc(i); for(int i=1;i<n;i++){ int u=e[i].u,v=e[i].v; if(col[u]==col[v]&&col[u]==2)calc(u,v,e[i].w); } cout<<ans; }