【luogu3174】 [HAOI2009]毛毛虫 [动态规划树形dp]

亦凉 2021-11-16 05:42 271阅读 0赞

[3174 \[HAOI2009\]毛毛虫][3174_HAOI2009]

求一条链链上的节点和与链上节点相连的兄弟和最大

在链上每个节点都被多算了一次 所以初设为1 虽然还没有搞清为什么要像树的直径一样跑两遍...

#include<bits/stdc++.h>
    using namespace std;
    #define Max(x,y) (x)<(y)?(y):(x)
    #define Min(x,y) (x)<(y)?(x):(y)
    #define ll long long
    #define rg register
    const int N=300000+5,M=1000000+5,inf=0x3f3f3f3f,P=9999973;
    int n,m,out[N],mxl=0,sf,ans=0;
    template <class t>void rd(t &x){
        x=0;int w=0;char ch=0;
        while(!isdigit(ch)) w|=ch=='-',ch=getchar();
        while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
        x=w?-x:x;
    }
    
    int head[N],tot=0;
    struct edge{
        int v,nxt;}e[N<<1];
    void add(int u,int v){
        e[++tot]=(edge){v,head[u]},head[u]=tot;
    }
    
    void dfs(int u,int fa,int dis){
        if(dis>=mxl) mxl=dis,sf=u;
        ans=Max(ans,dis);
        for(int i=head[u];i;i=e[i].nxt)
        if(fa!=e[i].v) dfs(e[i].v,u,dis+out[u]);
    }
    
    int main(){
        freopen("in.txt","r",stdin);
        rd(n),rd(m);
        memset(out,-1,sizeof(out));
        for(int i=1,u,v;i<=m;++i) rd(u),rd(v),add(u,v),add(v,u),++out[u],++out[v];
        dfs(1,0,0);mxl=-1,ans=0;
        dfs(sf,0,0);
        printf("%d",ans+2);
        return 0;
    }

转载于:https://www.cnblogs.com/lxyyyy/p/11210299.html

[3174_HAOI2009]: https://www.luogu.org/problemnew/show/P3174

发表评论取消回复

表情：

评论列表（有 0 条评论，271人围观）

还没有评论，来说两句吧...

相关阅读

相关动态规划dp专题

dp专题斐波那契数列 01背包问题最长不重复子字符串的长度分割数组的最大值最长公共子序列最大子序和买卖股票的最佳时期

爱被打了一巴掌/ 2023年07月17日 09:57/ 0 赞/ 26 阅读

相关动态规划-树形DP

文章目录树形DP HDU-1520 HDU-2196 树形DP -------------------- 树形DP，顾名思义是在「树」这种数

淩亂°似流年/ 2023年03月04日 06:40/ 0 赞/ 214 阅读

相关动态规划-数位DP

文章目录数位DP 例题 HDU-2089 法一、递推公式法二、记忆化搜索 HDU-35

- 日理万妓/ 2022年11月25日 11:58/ 0 赞/ 148 阅读

相关 DP动态规划算法理解

DP动态规划算法理解学习了DP动态规划算法，对动态规划也有了一点理解，动态规划是将原来的一个

短命女/ 2022年05月17日 00:17/ 0 赞/ 239 阅读

相关 [树形dp] Luogu P4516 潜入行动

题目描述外星人又双叒叕要攻打地球了，外星母舰已经向地球航行！这一次，`JYY` 已经联系好了黄金舰队，打算联合所有 `JSOIer` 抵御外星人的进攻。在黄金舰队就

电玩女神/ 2021年12月03日 22:51/ 0 赞/ 226 阅读

相关【luogu3174】 [HAOI2009]毛毛虫 [动态规划树形dp]

[3174 \[HAOI2009\]毛毛虫][3174_HAOI2009] 求一条链链上的节点和与链上节点相连的兄弟和最大在链上每个节点都被多算了一次所以初设为1 虽

亦凉/ 2021年11月16日 05:42/ 0 赞/ 272 阅读

相关【luogu1220】关路灯 [动态规划区间dp]

[P1220 关路灯][P1220] 一道区间dp 先预处理出关掉了第i~j盏灯时的功率然后f\[i\]\[j\]\[0/1\]表示关到灯i~j此时在左边(0)或右边(

朴灿烈づ我的快乐病毒、/ 2021年11月16日 05:40/ 0 赞/ 281 阅读

相关 luogu P2014 选课（树形dp）

[传送门][Link 1] 题意：现在有很多门课程，但是每门课程都会依赖某些其他的课程（即学了第\\(a\_i\\)门课程之后才能学习第\\(a\_\{i+1\}\\

女爷i/ 2021年11月05日 13:16/ 0 赞/ 390 阅读

相关算法——动态规划(DP）

动态规划问题，大致可以通过以下四部分进行解决：划分阶段：按照问题的时间或空间特征，把问题分为若干个子阶段。（划分后的子阶段一定要是有序的或者是可排序的，否则问题就无法

谁践踏了优雅/ 2021年10月18日 09:48/ 0 赞/ 444 阅读

相关 DP动态规划专题（一）动态规划基本模型

> 动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不像前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设

桃扇骨/ 2021年09月22日 23:28/ 0 赞/ 1000 阅读