GalaxyOJ-673 (dfs)

题目

Problem Description

ZSX非常嫉妒YZH走上了人生巅峰，于是他也狂刷BZOJ，终于感动了上天，实现了他的三个愿望：出任CEO、迎娶白富美、瘦身30斤，走上了人生巅峰，所以他决定来一次长途旅行好好放松一下。

由于经费问题，ZSX决定仅在CW国完成旅行。CW国一共有n个城市，这n个城市恰好构成一棵树，由于经费实在有限，ZSX决定仅去三个城市，又因为他是一个富有情趣的人，所以他不希望自己去的三个城市在同一条路径上出现。现在ZSX想知道他能去的三个城市有多少种组合。

Input

第一行一个正整数n，表示CW国的城市数量。

接下来n - 1行，每行两个正整数u,v，表示从城市u，v之间有一条树边。

对于100%的数据，n <= 100000, 1 <= u, v <= n

Output

一行一个数，表示答案。

Sample Input

5
1 2
1 3
2 4
2 5

Sample Output

2

【样例解释】

{{4,5,3},{4,5,1}}

分析

• 题目大概就是问一棵树里面有多少组点（每组三个点），使得它们（那三个点）不在一条链上。
• 我们可以把问题转换一下，变成求在一条链上的点的组数。（正着求答案也是可以的，只不过分类较多，容斥一下更方便）
• 搜索，枚举路径中间那个点，然后用些技巧可以求出路径数。

程序

#include 
#define For(x) for (int h=head[x],o=V[h]; h; o=V[h=to[h]])
#define C3(x) ((x)*(x-1)*(x-2)/6)
int head[100005],to[200005],V[200005],num;
long long n,sz[100005],a[100005],ds,Ans;void add(){int u,v; scanf("%d%d",&u,&v);to[++num]=head[u], head[u]=num, V[num]=v;to[++num]=head[v], head[v]=num, V[num]=u;
}long long dfs(int x,int Fa){sz[x]=1;For(x) if (o!=Fa){ds=dfs(o,x);a[x]+=(sz[x]-1)*sz[o];      //新的点加之前子树内的一个点可以与 x 组成一个路径 sz[x]+=ds;}a[x]+=(sz[x]-1)*(n-sz[x]);      //子树 x(x除外) 中的点加子树 x 外的点与 x 组成一个路径 Ans-=a[x];                      //这些都是不符合的，减掉它们 return sz[x];
}int main(){freopen("1.txt","r",stdin);scanf("%d",&n); for (int i=1; i//先把答案初始化成所有点的 组数 dfs(1,1);               //手动把1当成树的根printf("%lld",Ans);
}

提示

• 数据范围让我们需要开 long long。
• 时间复杂度估计是 2n
• 你们可以想一想这题拓展：把每组三个点变成 k 个点，复杂度在 nk 级别。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！