Description：

一棵 $n$ 个节点的树。在每个叶子节点有 $g$ 群蚂蚁进来，第 $i$ 群有 $m[i]$ 只蚂蚁。在离开某个度数为 $d+1$ 的点时，该群蚂蚁会分成 $d$ 组，每组有 $\lfloor\frac m d\rfloor$ 只，如果一群数量恰为 $k$ 只的蚂蚁通过某条边就会被吞掉。求有几只蚂蚁会被吞掉。

$1\leqslant n\leqslant 10^6$

Solution：

直接求很不好求，因为每个叶子节点都有，这就是这道题和一般树形 $DP$ 不一样的地方，就是他是从那条边往叶子节点递推，同时维护一个到这个点会被吃掉的区间，这样如果到了叶子，就在序列中二分出区间统计即可，注意可能会爆 $\text{long long}$ 所以要处理一下。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

typedef long long ll;

inline ll read()

{

	register ll res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m;

ll v;

#define MAXN 1000010

ll w[MAXN];

int deg[MAXN];

struct edge

{

	int to,nxt;

	bool tag;

}e[MAXN << 1];

int edgenum = 1;

int lin[MAXN] = {0};

void add(int a,int b,bool tag)

{

	++deg[a];++deg[b];

	++edgenum;e[edgenum].to = b;e[edgenum].tag = tag;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].tag = tag;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

int x,y;

ll ans = 0;

void dp(int k,ll l,ll r)

{

	int t = 0;

	ll l_ = min(l * (deg[k] - 1),1000000010ll),r_ = min(r * (deg[k] - 1) + (deg[k] - 2),1000000010ll); 

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

	{

		if(e[i].tag)continue;

		e[i].tag = e[i ^ 1].tag = true;

		dp(e[i].to,l_,r_);

		++t;

	}

	if(t == 0)

	{

		int lef = lower_bound(w + 1,w + 1 + m,l) - w,rig = upper_bound(w + 1,w + 1 + m,r) - w - 1;

		ans += rig - lef + 1;

	}

	return;

}

int main()

{

	scanf("%d%d%lld",&n,&m,&v);

	for(int i = 1;i <= m;++i)w[i] = read();

	w[++m] = 0x3f3f3f3f3f3f3f3f;

	sort(w + 1,w + 1 + m);

	int a,b;

	memset(deg,0,sizeof(deg));

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

	{

		a = read();b = read();

		bool tag;

		if(i == 1)x = a,y = b,tag = true;

		else tag = false;

		add(a,b,tag);

	}

	dp(x,v,v);dp(y,v,v);

	cout << ans * v << endl;

	return 0;

}