Description：

给定一个以 $1$ 为根的有根树求所有元素没有祖先后代关系的集合的价值和，集合的价值是集合内点权和。

$1\leqslant n\leqslant 10^6$

Solution：

设 $f[i]$ 表示子树 $i$ 内这样的集合的价值和， $g[i]$ 表示这样的集合的个数，则枚举子树时的转移方程为： $$ \begin{align} f[k]&=f[k]\times g[e[i].to]+f[e[i].to]\times g[k]\\ g[k]&=g[k]\times g[e[i].to] \end{align} $$ 最后再加上只选一个子树根的情况，即： $$ \begin{align} f[k]&+=val[k]\\ g[k]&+=1 \end{align} $$

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,t;

#define MAXN 1000010

int val[MAXN];

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

#define MOD 100000007

int f[MAXN],g[MAXN];

bool v[MAXN];

void dp(int k)

{

	v[k] = true;

	g[k] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		dp(e[i].to);

		f[k] = (1ll * f[k] * g[e[i].to] % MOD + 1ll * f[e[i].to] * g[k] % MOD) % MOD;

		g[k] = (1ll * g[k] * g[e[i].to]) % MOD;

	}

	++g[k];

	f[k] += val[k];

	return;

}

int main()

{

	scanf("%d%d",&n,&t);

	if(t == 0)for(int i = 1;i <= n;++i)val[i] = 1;

	else for(int i = 1;i <= n;++i)val[i] = i;

	int a,b;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	dp(1);

	cout << f[1] << endl;

	return 0;

}