2016 장락캠프 Day13

T1:
만약 x>=y라면 답은 분명하다(n-1)*y는 국화도를 특판할 뿐이다
만약 x < y, 문제는 한 나무에 가능한 한 많은 선택 체인이 된다
f[i][k]는 i를 뿌리로 하는 자수를 대표하고, i연변의 상태는 k로 가장 많이 선택한 변의 수량을 대표한다.
k <= 2
전이 가 분명하다

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

typedef long long LL;
const int maxn = 1E6 + 10;
const int INF = 1E9;

int n,du[maxn];
LL x,y,ans,f[maxn][3];

vector  v[maxn];

int dfs(int x,int fa)
{
	f[x][0] = f[x][1] = f[x][2] = 0;
	int x1,x2,res,r,son;
	x1 = x2 = -INF; son = 0;
	for (int i = 0; i < v[x].size(); i++) {
		int to = v[x][i];
		if (to == fa) continue;
		++son;
		f[x][0] += (r = dfs(to,x));
		res = max(f[to][0],f[to][1]) - r;
		if (res >= x1) {
			x2 = x1;
			x1 = res;
		}
		else if (res > x2) x2 = res;
	}
	if (son > 0) f[x][1] = max(f[x][0] + x1,0LL) + 1;
	if (son > 1) f[x][2] = max(f[x][0] + x1 + x2,0LL) + 2;
	return max(f[x][0],max(f[x][1],f[x][2]));
}

int main()
{
	#ifdef DMC
		freopen("DMC.txt","r",stdin);
    #else
		freopen("travel.in","r",stdin);
		freopen("travel.out","w",stdout);
	#endif
	
	cin >> n >> x >> y;
	for (int i = 1; i < n; i++) {
		int a,b; scanf("%d%d",&a,&b);
		v[a].push_back(b);
		v[b].push_back(a);
		++du[a]; ++du[b];
	}
	if (x >= y) {
		ans = 1LL*(n-1)*y;
		bool flag = 0;
		for (int i = 1; i <= n; i++)
			if (du[i] == n - 1) flag = 1;
		if (flag) ans += (x - y);
		cout << ans;
	}
	else {
		int Max = dfs(1,0);
		ans = 1LL*Max*x + 1LL*(n - 1 - Max)*y;
		cout << ans;
	}
	return 0;
}

T2: 보류 중
T3:
f[i]: 상태가 i인 점으로 구성된 합법적인 트리의 개수
g[i]: 상태가 i로 구성된 합법적인 삼림의 개
f[i]= ∑g[o-뿌리를 내리는 노드] 삼림: 삼림+새 나무 한 그루 g[i]= ∑f[op]*g[o-op]op은 반드시 o의 가장 왼쪽 수위를 포함하는 노드이다
초기값: g[0] = 1
처음엔 L, R이 아들 수인 줄 알았는데...바보스럽다

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

typedef long long LL;
const int maxn = 20;
const int maxm = 1<<15;
const LL mo = 1E9 + 7;

int n,L[maxn],R[maxn];
LL f[maxm],g[maxm];

int cal(int o)
{
	int ret = 0;
	for (; o; o >>= 1)
		if (o & 1) ++ ret;
	return ret;
}

int main()
{
	#ifdef DMC
		freopen("DMC.txt","r",stdin);
    #else
		freopen("tree.in","r",stdin);
		freopen("tree.out","w",stdout);
	#endif
	
	cin >> n;
	for (int i = 1; i <= n; i++) scanf("%d%d",&L[i],&R[i]);
	g[0] = 1;
	for (int o = 1; o < (1< 1) g[o] = f[o];
		for (int op = (opt - 1) & opt; op; op = (op - 1) & opt)
			g[o] = (g[o] + f[(1<