P4084 [USACO17DEC]Barn Painting G

#include<bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
class DP_on_tree{
public:
	#define ll long long
	ll n,k;
	ll free[100001];
	ll    f[100001][4];
	ll  vis[100001];
	vector < ll > e[100001];
	void DP(ll x,ll fa)
	{
		if(vis[x]==1) return;
		else          vis[x]=1;
		for(ll i=1; i<=3; i++)
		{
			if(free[x]!=0&&free[x]!=i){f[x][i]=0;continue;}
			f[x][i]=1;
			for(ll j=0; j<e[x].size(); j++)
			{
				ll y=e[x][j],res=0;
				if(y==fa)continue;
				DP(y,x);
				for(ll k=1; k<=3; k++)
				{
					if(free[y]!=0&&free[y]!=k)continue;
					if(k==i)continue;
					res+=f[y][k];
					res%=mod;
				}
				f[x][i]*=res;
				f[x][i]%=mod;
			}
		}
	}
	void Main()
	{
		scanf("%lld%lld",&n,&k);
		for(ll i=1,x,y; i<n; i++)
		{
			scanf("%lld%lld",&x,&y);
			e[x].push_back(y);
			e[y].push_back(x);
			vis[i]=0;
		}
		vis[n]=0;
		for(ll i=1,b,co; i<=k; i++)
		{
			scanf("%lld%lld",&b,&co);
			free[b]=co;
		}
		DP(1,0);
		printf("%lld\n",(f[1][1]+f[1][2]+f[1][3])%mod);
	}
}x;
int main()
{
	x.Main();
}