题解：洛谷 P11251 [GESP202409 八级] 美丽路径

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P11251 [GESP202409 八级] 美丽路径 - 洛谷【题目描述】小杨有一棵包含n nn个节点的树节点从1 11到n nn编号并且每个节点要么是白色要么是黑色。对于树上的一条简单路径不经过重复节点的路径小杨认为它是美丽的当且仅当路径上相邻节点的颜色均不相同。例如下图其中节点1 11和节点4 44是黑色其余节点是白色路径2 − 1 − 3 − 4 2-1-3-42−1−3−4是美丽路径而路径2 − 1 − 3 − 5 2-1-3-52−1−3−5不是美丽路径相邻节点3 33和5 55颜色相同。对于树上的一条简单路径小杨认为它的长度是路径包含节点的数量。小杨想知道最长的美丽路径的长度是多少。【输入】第一行包含一个正整数n nn代表节点数量。第二行包含n nn个整数c 1 , c 2 , … , c n c_1,c_2,\dots,c_nc1​,c2​,…,cn​代表每个节点的颜色如果c i 0 c_i0ci​0代表节点i ii为白色如果c i 1 c_i1ci​1代表节点i ii为黑色。之后n − 1 n-1n−1行每行包含两个正整数u i , v i u_i,v_iui​,vi​代表存在一条连接节点u i u_iui​和节点v i v_ivi​的边。【输出】输出一个整数代表最长美丽路径的长度。【输入样例】5 1 0 0 1 0 1 2 3 5 4 3 1 3【输出样例】4【核心思想】问题分析给定一棵n nn个节点的树每个节点为黑色或白色。求最长美丽路径长度——即路径上相邻节点颜色均不相同的简单路径的节点数最大值。本质是一个带颜色约束的树直径问题需要找到颜色交替的最长链。算法选择树形DP换根思想的简化版对每个节点u uu维护以u uu为端点的最长和次长美丽路径长度通过子树信息合并计算经过u uu的最长路径关键观察最长美丽路径要么完全在某棵子树内递归求解要么经过当前节点u uu连接两个不同子树的路径f 1 [ u ] f 2 [ u ] f1[u] f2[u]f1[u]f2[u]关键步骤建图与初始化用邻接表存储树读取节点颜色c [ 1.. n ] c[1..n]c[1..n]DFS树形DP参数u uu为当前节点fa \text{fa}fa为父节点遍历子节点对于u uu的每个邻接节点j jj跳过父节点fa \text{fa}fa递归计算子树信息DFS ( j , u ) \text{DFS}(j, u)DFS(j,u)颜色判定转移若c [ u ] ≠ c [ j ] c[u] \neq c[j]c[u]c[j]颜色不同可延续美丽路径则t f 1 [ j ] 1 t f1[j] 1tf1[j]1否则t 0 t 0t0路径断裂维护最长与次长将t tt与f 1 [ u ] f1[u]f1[u]、f 2 [ u ] f2[u]f2[u]比较更新保持f 1 [ u ] ≥ f 2 [ u ] f1[u] \geq f2[u]f1[u]≥f2[u]更新全局答案ans max ⁡ ( ans , f 1 [ u ] f 2 [ u ] ) \text{ans} \max(\text{ans}, f1[u] f2[u])ansmax(ans,f1[u]f2[u])表示经过u uu的最长美丽路径由两条子链拼接而成结果转换树形DP中f 1 , f 2 f1, f2f1,f2记录的是边数最终答案为ans 1 \text{ans} 1ans1转换为节点数时间/空间复杂度时间复杂度O ( n ) O(n)O(n)每个节点只访问一次每条边只处理一次空间复杂度O ( n ) O(n)O(n)邻接表和DP数组空间树形DP求带约束直径的核心思想子树信息上传f 1 [ u ] f1[u]f1[u]表示以u uu为端点、向下延伸的最长美丽路径的边数通过子节点的f 1 [ j ] f1[j]f1[j]转移得到颜色断点处理当c [ u ] c [ j ] c[u] c[j]c[u]c[j]时路径无法延续强制t 0 t 0t0确保美丽路径的相邻节点颜色交替直径拼接原理经过u uu的最长路径由u uu的两个不同子树中的最长链拼接而成因此维护最长和次长两个值边数转节点数DP过程中以边数计算最终答案加1 11转换为路径包含的节点数量适用于树上带约束的最长链、直径变形、颜色/权值限制的路径问题【算法标签】#普及 #树形DP【代码详解】#includebits/stdc.husingnamespacestd;constintN100005,MN*2;intn;// 节点数量intc[N];// c[i] 表示节点i的颜色intf1[N];// f1[i]: 以节点i为起点的最长同色路径长度intf2[N];// f2[i]: 以节点i为起点的次长同色路径长度intans;// 最终答案路径上的节点数-1即最大长度inth[N],e[M],ne[M],idx;// 邻接表存储树// 添加无向边voidadd(inta,intb){e[idx]b;ne[idx]h[a];h[a]idx;}// 深度优先搜索// u: 当前节点// fa: 父节点voiddfs(intu,intfa){// 遍历所有邻接节点for(intih[u];i!-1;ine[i]){intje[i];// 邻接节点if(jfa)// 跳过父节点{continue;}// 递归处理子树dfs(j,u);// 计算从当前节点u到子节点j的路径长度// 如果u和j颜色不同路径长度为f1[j]1否则为0intt(c[u]!c[j]?f1[j]1:0);// 更新f1[u]和f2[u]if(tf1[u]){f2[u]f1[u];// 原来的最大值变为次大值f1[u]t;// 更新最大值}elseif(tf2[u]){f2[u]t;// 更新次大值}}// 更新答案考虑经过节点u的最长同色路径// 注意这里计算的是路径上的边数而不是节点数ansmax(ans,f1[u]f2[u]);}intmain(){cinn;// 初始化邻接表memset(h,-1,sizeof(h));idx0;// 读取每个节点的颜色for(inti1;in;i){cinc[i];}// 读取树的边for(inti1;in;i){intu,v;cinuv;add(u,v);add(v,u);}// 从节点1开始DFSdfs(1,0);// 输出结果最长同色路径的节点数 边数 1coutans1endl;return0;}【运行结果】5 1 0 0 1 0 1 2 3 5 4 3 1 3 4