[CF161D]Distance in Tree-树状dp

Problem Distance in tree

题目大意

给出一棵树，求这棵树上有多少个最短距离为k的点对。

Solution

这个题目可以用点分治来做，然而我到现在还是没有学会点分治，所以只好用树形dp了。

这个题目，我们可以将其转化为一个个子树中搞事情，再慢慢合并。

设f[i][j]为以i为根的子树中距离根距离为j的点有多少个。

对于一个点u，我们枚举它的子节点v，则我们可以计算出经过u-v这条边的答案

我们枚举j=1->k，则ans+=f[u][j]*f[v][k-j-1];

枚举完以后，我们将这一棵子树合并到u节点去，以便统计u的其它子树。

具体过程我们只需要dfs一遍，对于每个叶子结点x，f[x][0]=1。

然后不断向上回溯，边回溯边进行如上计算，最后即可算出正确答案。

具体可以参考一下代码。

AC Code

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 struct node{

     int to,next;

 }e[];

 int n,k,u,v,ans=,tot=;

 int h[],f[][];

 void add(int u,int v){

     e[++tot].to=u;e[tot].next=h[v];h[v]=tot;

     e[++tot].to=v;e[tot].next=h[u];h[u]=tot;

 }

 void dfs(int x,int last){

     f[x][]=;

     for(int i=h[x];~i;i=e[i].next){

         if(e[i].to!=last){

             dfs(e[i].to,x);

             for(int j=;j<k;j++)ans+=f[x][j]*f[e[i].to][k-j-];

             for(int j=;j<=k;j++)f[x][j]+=f[e[i].to][j-];

         }

     }

 }

 int main(){

 //  freopen("cf161d.in","r",stdin);

     memset(h,-,sizeof(h));

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

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

         scanf("%d%d",&u,&v);

         add(u,v);

     }

     dfs(,);

     printf("%d",ans);

 }

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <cstring>

 4 using namespace std;

 5 struct node{

 6     int next,to;

 7 }e[200010];

 8 bool neko[100010];

 9 int n,m,d,x,u,v,path[100010],h[100010],ans=0,tot=0;

10 int pathp[100010],pathn[100010];

11 void add(int u,int v){

12     e[++tot].to=u;e[tot].next=h[v];h[v]=tot;

13     e[++tot].to=v;e[tot].next=h[u];h[u]=tot;

14 }

15 void dfspath(int x,int last){

16     path[x]=-2333333;pathp[x]=-2333333;

17     for(int i=h[x];~i;i=e[i].next){

18         if(e[i].to!=last){

19             dfspath(e[i].to,x);

20             if(path[x]<path[e[i].to]+1){

21                 pathp[x]=path[x];

22                 path[x]=path[e[i].to]+1;

23                 pathn[x]=e[i].to;

24             }else if(pathp[x]<path[e[i].to]+1)pathp[x]=path[e[i].to]+1;

25         }

26     }

27     if(neko[x]&&path[x]<-2000000)path[x]=0;

28     if(neko[x]&&pathp[x]<-2000000)pathp[x]=0;

29 }

30 void dpdfs(int x,int last){

31     if(~last)

32     if(pathn[last]==x){

33         if(pathp[last]+1>path[x]){

34             pathp[x]=path[x];

35             path[x]=pathp[last]+1;

36             pathn[x]=0;

37         }else if(pathp[last]+1>pathp[x])pathp[x]=pathp[last]+1;

38     }else{

39         if(path[last]+1>path[x]){

40             pathp[x]=path[x];

41             path[x]=path[last]+1;

42             pathn[x]=0;

43         }else if(path[last]+1>pathp[x])

44             pathp[x]=path[last]+1;

45     }

46     if(path[x]<=d)ans++;

47     for(int i=h[x];~i;i=e[i].next)

48         if(e[i].to!=last)dpdfs(e[i].to,x);

49 }

50 int main(){

51 //  freopen("cf337d.in","r",stdin);

52     memset(h,-1,sizeof(h));

53     scanf("%d%d%d",&n,&m,&d);

54     for(int i=1;i<=m;i++)

55         scanf("%d",&x),neko[x]=1;

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

57         scanf("%d%d",&u,&v);

58         add(u,v);

59     }

60     dfspath(1,1);

61     dpdfs(1,-1);

62     printf("%d",ans);

63 }