首页 > > 程序设计 > C/C++ >

Distance in Tree CodeForces - 161D

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

题意：给一棵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 }