每日一题 TreePath 树形dp+合并

Treepath

https://ac.nowcoder.com/acm/problem/14248

链接:https://ac.nowcoder.com/acm/problem/14248
来源:牛客网

Treepath
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 32768K,其他语言65536K
64bit IO Format: %lld

题目描述

给定一棵n个点的树,问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同。

输入描述:

第一行一个数n表示点的个数;
接下来n-1行,每行两个整数x,y表示边;
保证输入数据形成一棵树;
1<=n<=100000

输出描述:

一行一个整数表示答案。
示例1

输入

复制 3 1 2 1 3
3
1 2
1 3

输出

复制 1
1


求偶数长度的路径有多少条
 
首先将题目转换一下:求点数为奇数的路径有多少条

然后将奇数的路径分为,从每个结点出发向下的奇数的路径与向上的奇数路径,向上的奇数路径就可以根据 合并的思想,将每个节点作为中间节点过度一下即可:

具体使用
dp[i][1]表示从i出发,长度为奇数个点的路径数 
dp[i][0]表示从i出发 ,长度为偶数个点的路经数

转移显然:
dp[u][1]+=dp[e][0]  ///当前节点作为一个点
dp[u][0]+=dp[e][1]

中间启发合并过度节点 只需要记录在访问节点前的偶数节点个数与奇数节点个数即可:

Code:

/*** keep hungry and calm CoolGuang!***/
//#pragma GCC optimize(2)
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pp;
const ll INF=1e17;
const int maxn=3e5+6;
const int mod=20020421;
const double eps=1e-3;
inline bool read(ll &num)
{char in;bool IsN=false;
in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
ll dp[maxn][2];
ll ans=0;
vector<int>v[maxn];
void dfs(int u,int fa){
    dp[u][1]=1;
    ll a=0,b=0;
    for(int e:v[u]){
        if(e==fa) continue;
        dfs(e,u);
        dp[u][1]+=dp[e][0];
        dp[u][0]+=dp[e][1];
        ans+=dp[e][0]*a;
        ans+=dp[e][1]*b;
        a+=dp[e][0];
        b+=dp[e][1];
    }
}
int main()
{
    read(n);
    for(int i=1;i<=n-1;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,1);
    for(int i=1;i<=n;i++)
        ans+=dp[i][1];
    printf("%lld\n",ans-n);
    return 0;
}

/***
1 2 3 4 5
***/



















全部评论

相关推荐

不愿透露姓名的神秘牛友
07-21 13:38
8月实习会变多吗现在还没找到实习该怎么办...回复的hr好少
码农索隆:3-4月就要开始找,基本上6月份就发offer,7月初已经开始暑期实习了。
点赞 评论 收藏
分享
06-13 17:33
门头沟学院 Java
顺序不记了,大致顺序是这样的,有的相同知识点写分开了1.基本数据类型2.基本数据类型和包装类型的区别3.==和equals区别4.ArrayList与LinkedList区别5.hashmap底层原理,put操作时会发生什么6.说出几种树型数据结构7.B树和B+树区别8.jvm加载类机制9.线程池核心参数10.创建线程池的几种方式11.callable与runnable区别12.线程池怎么回收线程13.redis三剑客14.布隆过滤器原理,不要背八股,说说真正使用时遇到了问题没有(我说没有,不知道该怎么回答了)15.堆的内存结构16.自己在写项目时有没有遇见过oom,如何处理,不要背八股,根据真实经验,我说不会17.redis死锁怎么办,watchdog机制如何发现是否锁过期18.如何避免redis红锁19.一个表性别与年龄如何加索引20.自己的项目的QPS怎么测的,有没有真正遇到大数量表21.说一说泛型22.springboot自动装配原理23.springmvc与springboot区别24.aop使用过嘛?动态代理与静态代理区别25.spring循环依赖怎么解决26.你说用过es,es如何分片,怎么存的数据,1000万条数据怎么写入库中27.你说用limit,那么在数据量大之后,如何优化28.rabbitmq如何批次发送,批量读取,答了延迟队列和线程池,都不对29.计网知不知道smtp协议,不知道写了对不对,完全听懵了30.springcloud知道嘛?只是了解反问1.做什么的?短信服务,信息量能到千万级2.对我的建议,基础不错,但是不要只背八股,多去实际开发中理解。面试官人不错,虽然没露脸,但是中间会引导我回答问题,不会的也只是说对我要求没那么高。面完问我在济宁生活有没有困难,最快什么时候到,让人事给我聊薪资了。下午人事打电话,问我27届的会不会跑路,还在想办法如何使我不跑路,不想扣我薪资等。之后我再联系吧,还挺想去的😭,我真不跑路哥😢附一张河科大幽默大专图,科大就是大专罢了
查看30道真题和解析
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务