【SCOI2019】—DAY2T1 RGB（容斥）

发现就是傻逼论文题，或者今年九省联考的希望看了题解也就知道这道题怎么容斥了

具体方法是考虑$点数=边数-1$

直接统计每个$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;
}