牛客练习赛97 D(经典树形dp不会)

题目 题意: 给定一棵n个点的树，有x种普通颜色，y种特殊颜色。现在要进行染色，普通颜色染色没有限制，特殊颜色染色时要求相邻两个节点不能染相同的特殊颜色。 思路: 树形dp. f[cur][0] = Π (xf[son][0] + yf[son][1]) f[cur][1] = Π (x*f[son][0] + (y-1)*f[son][1]) 时间复杂度: O(n) 代码:

// Problem: 月之暗面
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/30030/D
// Memory Limit: 524288 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;iT;
   // read(T);
   while(T--)
   {
   	 solve();
   }
   return 0;
}