【XSY2410】【CF486D】有效集合（树形dp）

(Description)

给你一颗(n)个点的树，每个点有一个权值(a[i]),求出这颗树的所有满足

权值最大点的权值-权值最小点的权值(<=d)的联通子图的数目，答案对(10^9+7)取模

---

(Input)

第一行，两个整数(d,n)

第二行，(n)个整数(a[1]…a[n])

第(3sim n+1)行，每行两个整数(x,y)，表示(x)和(y)间有一条边

---

(Output)

一行，一个整数，表示答案对(10^9+7)取模后的值

---

(Sample Input)

4 8
7 8 7 5 4 6 4 10
1 6
1 2
5 8
1 3
3 5
6 7
3 4

---

(Sample Output)

41

---

(HINT)

(0<=d<=2000,1<=n<=2000,1<=a[i]<=2000)

---

(Source)

 练习题　树1-树形DP

---

思路

我们可以发现(n)的范围十分的小，所以我们考虑对于每个节点作为根进行(dfs)

对于每一个根(rt)，我们假设这个(rt)是最小值，在(dfs)的过程中，我们要一直保证(rt)为最小值，所以不去遍历小于(rt)的值

然后我们考虑什么时候可以遍历他的儿子(v)

首先要满足我们上面提到的 (a[v]>a[rt])

接着，还要满足题目给出的条件权值最大点的权值-权值最小点的权值(<=d)

所以我们还要有一个条件： (a[v]-a[rt]<=d)

满足条件的(v)就可以对答案进行更新：(ans=(ans*(dfs(v,u,rt)+1)\%mod)\%mod)

然后快乐打完代码后

就会发现可喜可贺的

为什么呢？

(After) (two) (years)，我们会发现，有些答案会被计算两遍！？

我们分析可得：当(a[v]=a[rt])时， (v) 和 (rt) 会重复计算两遍，所以我们要给它们一个顺序，即当(rt>v)时再统计答案，这样就可以做完啦

---

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2010,mod=1e9+7;;
int d,n,cnt=0;
int a[N];
int to[N<<1],nxt[N<<1],head[N];
void add(int u,int v)
{
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}
ll dfs(int u,int fa,int rt)
{
    ll ans=1ll;
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        if(v==fa)continue;
        if((a[v]>a[rt]||(a[v]==a[rt]&&rt>v))&&(a[v]-a[rt])<=d)
        {
            ans=(ans*(dfs(v,u,rt)+1)%mod)%mod;
        }
    }   
    return ans;
}
int main()
{
    scanf("%d %d",&d,&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    int x,y;
    for(int i=1;i<n;i++)
    {
        scanf("%d %d",&x,&y);
        add(x,y);add(y,x);
    }
    ll output=0ll;
    for(int i=1;i<=n;i++)output=(output+dfs(i,0,i))%mod;
    printf("%lld",output);
    return 0;
}