知识屋：更实用的电脑技术知识网站
知识屋 手机游戏 手机软件 电脑软件 最近更新 手机端
冒险村物语 英雄无敌3塔防 驾考家园手游 我的小家破解版 业力汉堡商店
cah职工e家 智能安全管控 易慧 iedukids学习中 闪背
亿彩文本文件批 文件自动分类器（ Win8激活信息备
LOL手游国服和外 LOL手游日服怎么 怎么注册LOL手游 2020双十一活动
所在位置：首页 > 编程技术  > PHP编程

hdu 4705 树形dp

发表时间：2015-05-27来源：网络

题意：树上任意三个点不在一条路径上，统计这样的三点集合有多少种。
三个点构成的路方案数 S = C(n,3)=n*(n-1)*(n-2)/6
用S减去三个点在一条路径上的数目就是答案。
枚举中间点作为第二个点，在它的第K棵子树上找一个点作为第一个点，在剩下的，没有枚举过的结点里，找一个点作为第三个点。数目相乘。
这样问题就变成了统计结点的子节点问题，简单的树形dp。
#include <iostream>  
#include <cstdio>  
#include <algorithm>  
#include<cstdio>  
#include<cstring>  
#include<vector>  
#pragma comment(linker,"/STACk:102400000,102400000")  
using namespace std;  
vector<int> tree[100005];  
typedef long long ll;  
ll ans,ll n;  
ll dfs(int k,int fa=-1)  
{  
    ll sum=0,son=0;  
    for(int i=0;i<tree[k].size();i++)  
        if(tree[k][i]!=fa){  
            sum+=son=dfs(tree[k][i],k);  
            ans+=son*(n-sum-1);  
        }  
    return sum+1;  
}  
int main()  
{  
    int a,b;  
    while(cin>>n)  
    {  
        for(int i=1;i<=n;i++) tree[i].clear();  
        for(int i=1;i<n;i++)  
        {  
            scanf("%d%d",&a,&b);  
            tree[a].push_back(b);  
            tree[b].push_back(a);  
        }  
        ans=0;  
        dfs(1);  
        cout<<n*(n-1)*(n-2)/6-ans<<endl;  
    }  
    return 0;  
}  
（免责声明：文章内容如涉及作品内容、版权和其它问题，请及时与我们联系，我们将在第一时间删除内容，文章内容仅供参考）
收藏

上一篇：thinkphp 无线级别分类

下一篇：无刷新页面的消息提示功能

知识阅读

软件推荐

更多 >

游戏推荐

更多 >

精选栏目

热门推荐

  • 人气文章
  • 最新文章
  • 下载排行榜
  • 热门排行榜

手机游戏

手机软件

电脑软件

猜你喜欢

城市 智能 家居 福利 美女 壁纸 截图 照片 修图 新闻 八卦 免费 农业 司机 会议 物流 资源 拍摄 下载 美图 手机 宠物 计算机 服务 汽车 二手 程序员 短视频 播放器 影视 动漫 停车 江浙沪 地铁 公交 抖音 舞蹈 征信 母婴 低息 分期 钱包 区块链 360 投注 彩票 借贷 网贷 借钱 抢票 吃货 购物 WIFI 导航 运动 健康

本站所有软件来自互联网，版权归原著所有。如有侵权，敬请来信告知，我们将及时撤销。

知识屋 www.zhishiwu.com 更实用的电脑技术知识网站

苏ICP备14019037号-7

联系我们