前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Treepath

Treepath

作者头像
杨鹏伟
发布2020-09-10 20:04:22
3290
发布2020-09-10 20:04:22
举报
文章被收录于专栏:ypw

给定一棵n个点的树,问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同。 输入描述: 第一行一个数n表示点的个数; 接下来n-1行,每行两个整数x,y表示边; 保证输入数据形成一棵树; 1<=n<=100000 输出描述: 一行一个整数表示答案。

思路:题意:给出一棵树,求树上所有长度为偶数的路径个数 涉及知识点:树上dfs/dpdfs/dp 思路:以任意一个节点dfsdfs(默认以11号节点dfsdfs),因为树上任意两点之间的距离是固定的,所以我们可以dfsdfs得到所有距离11号节点的长度,存在两个结论(证明看下图): ①长度为偶数的任意两个节点之间的距离一定是偶数 ②长度为奇数的任意两个节点之间的距离也一定是偶数 最后记录距离11号节点长度为奇数的节点个数cnt1,距离11号节点长度为偶数的节点个数cnt2 答案就是(cnt1*(cnt1-1)/2) + (cnt2*(cnt2-1)/2)

在这里插入图片描述
在这里插入图片描述
代码语言:javascript
复制
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;
struct node{
int t,nex;
};
node a[maxn<<1];
int head[maxn],tot,cnt[maxn];
void add(int x,int y){
  a[++tot].t = y,a[tot].nex = head[x],head[x] = tot;
}
void dfs(int x,int fa,int len)
{
  cnt[x] = len;
  for(int i=head[x]; i ; i=a[i].nex){
      if(a[i].t != fa)
          dfs(a[i].t , x , len + 1);
  }
}
int main()
{
  int n,x,y,cnt1 = 0 ,cnt2 = 0;
  cin>>n;
  for(int i=1;i<n;i++)
      cin>>x>>y,add(x,y),add(y,x);
  dfs(1 , 0 , 0);
  for(int i=1;i<=n;i++){
      if(cnt[i]%2)cnt1++;
      else cnt2++;
  }
  cout<<(1ll*cnt1*(cnt1 - 1)/2) + (1ll*cnt2*(cnt2 - 1)/2)<<endl;
  return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020/05/13 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档