Distance in Tree CodeForces - 161D

2018-06-17 21:56:32来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

Distance in Tree CodeForces - 161D

题意:给一棵n个结点的树,任意两点之间的距离为1,现在有点u、v,且u与v的最短距离为k,求这样的点对(u,v)的个数((u,v)/(v,u)算一对)。

方法:

ans[i][k]表示与i结点距离为k的子结点个数

ans[i][k]=sum{ans[son][k-1]}

ans[i][0]=1

sum[i]表示(u,v)都为i的子结点且(u,v)的最短路径过i点

sum[i]=sum{ans[i][p]*ans[i][k-p]}//不对,会多计同一条链上的

sum[i]=sum{ans[son][p]*sum{ans[otherson][k-p-2]}}//对,但是太慢了

sum[i]=sum{ans[son][p]*(ans[i][k-p-1]-ans[son][k-p-2])}//换种写法(自己想不到)

由于(u,v)/(v,u)算一对,所以实际上i点有关的答案(也就是一个端点为i点,或(u,v)都为i的子结点且(u,v)的最短路径过i点)为:

$ans[i][k]+sum[i]/2$

由于不需要各个点分开记,可以直接用一个ans加上这些值,不用开sum。

 1 #include<cstdio>
 2 #include<vector>
 3 using namespace std;
 4 typedef long long LL;
 5 struct Edge
 6 {
 7     LL to,next;
 8 }edge[100001];
 9 LL first1[50010],num_edge;
10 LL ans[50001][501];
11 LL ans1,ans2,n,k2;
12 bool vis[50001];
13 void dfs(LL u)
14 {
15     LL k=first1[u],i,j;
16     vector<LL> temp;
17     ans[u][0]=1;
18     vis[u]=true;
19     while(k!=0)
20     {
21         LL &v=edge[k].to;
22         if(!vis[v])
23         {
24             dfs(v);
25             for(i=1;i<=k2;i++)
26                 ans[u][i]+=ans[v][i-1];
27             temp.push_back(v);
28         }
29         k=edge[k].next;
30     }
31     ans2+=ans[u][k2];
32     for(i=0;i<temp.size();i++)
33         for(j=0;j<=k2-2;j++)
34             ans1+=ans[temp[i]][j]*(ans[u][k2-j-1]-ans[temp[i]][k2-j-2]);
35 }
36 int main()
37 {
38     LL i,a,b;
39     scanf("%I64d%I64d",&n,&k2);
40     for(i=1;i<n;i++)
41     {
42         scanf("%I64d%I64d",&a,&b);
43         edge[++num_edge].to=b;
44         edge[num_edge].next=first1[a];
45         first1[a]=num_edge;
46         edge[++num_edge].to=a;
47         edge[num_edge].next=first1[b];
48         first1[b]=num_edge;
49     }
50     dfs(1);
51     printf("%I64d",ans2+ans1/2);
52     return 0;
53 }

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:hdu 6199 沈阳网络赛---gems gems gems(DP)

下一篇:hdu 6194 沈阳网络赛--string string string(后缀数组)