牛客练习赛97 D

直接树形 dp，记录当根节点颜色假如已经被确定时的两种方案对应方案数即可。

std::vector<uint>Way[1000005];
modint x,y;
modint Kind[1000005][2];
voi dfs(uint p,uint f)
{
    Kind[p][0]=Kind[p][1]=1;
    for(uint s:Way[p])if(s!=f)
    {
        dfs(s,p);
        Kind[p][0]*=Kind[s][0]*x+Kind[s][1]*y;
        Kind[p][1]*=Kind[s][0]*x+Kind[s][1]*(y-1);
    }
}
int main()
{
    uint n,u,v;scanf("%u",&n);x.read(),y.read();
    while(--n)
        scanf("%u%u",&u,&v),Way[--u].push_back(--v),Way[v].push_back(u);
    dfs(0,-1);
    (Kind[0][0]*x+Kind[0][1]*y).println();
	return 0;
}