树形DP 进阶题

84 阅读 0 评论 56 点赞

我是靠谱客的博主顺利凉面，这篇文章主要介绍树形DP 进阶题，现在分享给大家，希望可以做个参考。

emmmm我之前那篇博客都是一些普及提高的树形DP水题，基本都是一个模板能够解决的问题。现在让我们来进阶一下。
**

T1

HOT-Hotels

传送门

有一个树形结构，每条边的长度相同，任意两个节点可以相互到达。选3个点。两两距离相等。有多少种方案？

难度：省选+/NOI-
这道题的难度并不是不能接受，一开始会觉得很难但是仔细想过之后会发现其实还好。

首先，我们要求任意三个点互相到达的距离相等，同时它是一个树形结构
所以，仔细想一下可以得知，如果要让三个点互相距离相同，那么只会有一种方案，也就是，一个中心店，即他们到这个中心点距离相同，然后它们之间互相的距离也是一样的。
如果一时不能理解的话，请想过后再往下看。

那么，这个这个中心点就成为了我们做这道题的入手。
我们可以枚举这个树形结构的每一个点作为根，那么，在我们每次枚举出的这棵树里，每一层的节点是不是就是高度相同？
也就是，这些点每三个就可以作为一个方案，
然后我们的任务就是来求方案了
根据小学乘法原理，
譬如这个根有三个子树，在这一层的节点数分别是a,b,c，那么方案数是不是就是a*b*c？
同理如果这个根再多一个子树那么方案数是不是还要多
$a*b*d+a*c*d+b*c*d$
即 $(a*b+a*c+b*c)*d$
那么再多一颗子树也依然如此。

所以这就是我们的突破口了，
用一个sum2数组维护a*b+b*c+a*c………等这一式子；每次新得到的节点数为K
那么新增加的答案数为sum2*K;
设sum1为当前这一层当前子树之前的所有节点之和，
设tot[i]为当前子树第i层的节点数
那么框架就是
1.枚举根节点k
2.枚举每一棵子树，计算第i层的tot[i];
3.计算部分：
$ans=ans+tot[i]*sum2[i];$
$sum2[i]=sum2[i]+sum1[i]*tot[i]$
$sum1[i]=sum1[i]+tot[i]$
$tot[i]=0//清零**$

然后就是每次枚举树根之后，sum1sum2要清零。

代码：

复制代码

#include<bits/stdc++.h>
using namespace std;

const int maxn=5010;
int n,m,cnt,head[maxn],sum1[maxn],sum2[maxn],dep,tot[maxn];
long long ans;
inline int read()
{
    int X=0,w=0; char c=0;
    while(c<'0'||c>'9') {w|=c=='-';c=getchar();}
    while(c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar();
    return w?-X:X;
}

struct node
{
    int v,nxt;
}e[maxn<<1];

void add(int u,int v)
{
    cnt++;
    e[cnt].nxt=head[u];
    e[cnt].v=v;
    head[u]=cnt;
}
void getfun(int v,int u,int deep)
{
    dep=max(dep,deep);
    tot[deep]++;
    for (int i=head[v]; i; i=e[i].nxt)
      {
        int y=e[i].v; 
        if (y==u) continue;
        getfun(y,v,deep+1);
      }
}

int main()
{
    n=read();
    for (int i=1; i<n; i++)
      {
        int x,y;
        x=read(),y=read();
        add(x,y);
        add(y,x);
      }
    for (int i=1; i<=n; i++)
      {
        memset(sum1,0,sizeof(sum1));
        memset(sum2,0,sizeof(sum2));
        for (int j=head[i]; j; j=e[j].nxt)
          {
            int v=e[j].v;
            dep=0;
            getfun(v,i,1);
            for(int k=1;k<=dep;k++)
              {
               ans+=tot[k]*sum2[k];
               sum2[k]=sum2[k]+sum1[k]*tot[k];
               sum1[k]=sum1[k]+tot[k];
               tot[k]=0;
              }
          }
      }
    cout<<ans;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;

const int maxn=5010;
int n,m,cnt,head[maxn],sum1[maxn],sum2[maxn],dep,tot[maxn];
long long ans;
inline int read()
{
    int X=0,w=0; char c=0;
    while(c<'0'||c>'9') {w|=c=='-';c=getchar();}
    while(c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar();
    return w?-X:X;
}

struct node
{
    int v,nxt;
}e[maxn<<1];

void add(int u,int v)
{
    cnt++;
    e[cnt].nxt=head[u];
    e[cnt].v=v;
    head[u]=cnt;
}
void getfun(int v,int u,int deep)
{
    dep=max(dep,deep);
    tot[deep]++;
    for (int i=head[v]; i; i=e[i].nxt)
      {
        int y=e[i].v; 
        if (y==u) continue;
        getfun(y,v,deep+1);
      }
}

int main()
{
    n=read();
    for (int i=1; i<n; i++)
      {
        int x,y;
        x=read(),y=read();
        add(x,y);
        add(y,x);
      }
    for (int i=1; i<=n; i++)
      {
        memset(sum1,0,sizeof(sum1));
        memset(sum2,0,sizeof(sum2));
        for (int j=head[i]; j; j=e[j].nxt)
          {
            int v=e[j].v;
            dep=0;
            getfun(v,i,1);
            for(int k=1;k<=dep;k++)
              {
               ans+=tot[k]*sum2[k];
               sum2[k]=sum2[k]+sum1[k]*tot[k];
               sum1[k]=sum1[k]+tot[k];
               tot[k]=0;
              }
          }
      }
    cout<<ans;
}