[GESP202409 八级] 美丽路径

GESP编程共123题，本题是整站第1441题，已经有人完成了本题，加油！

题目描述

小杨有一棵包含 n 个节点的树，节点从 1 到 n 编号。每个节点要么是白色，要么是黑色。

对于树上的一条简单路径（不经过重复节点的路径），小杨认为它是美丽的当且仅当路径上相邻节点的颜色均不相同。例如下图，其中节点 1 和节点 4 是黑色，其余节点是白色，路径 2−1−3−4 是美丽路径，而路径 2−1−3−5 不是美丽路径（相邻节点和颜色相同）。

对于树上一条简单路径，小杨认为它的长度是路径包含的节点数量。小杨想知道最长美丽路径的长度是多少。

第一行包含一个正整数 n，表示节点数量。
第二行包含 n 个整数 c1,c2,c3,…cn，代表每个节点的颜色。如果 ci=0，节点 i 为白色；如果 ci=1，节点 i 为黑色。
之后 n−1 行，每行两个正整数 ui,vi，表示树上一条边。

输出一行一个整数表示答案。

输入 #1

输出 #1

输入 #2

输出 #2

对全部的测试数据，保证 1≤n≤10^5，0≤ci≤1，保证给出的是一棵树。

【题目大意】给定一棵树和节点颜色(黑白)，找出最长的一条黑白相间的链路对应的节点数量。

【考纲知识点】树形DP

【解题思路】对于30%的数据，直接建图暴力，可以得到30分

满分解：

1.定义DP[x][0/1]:x以x为根的,x颜色为(0白1黑)的最长链路节点数量
初始化:DP[x][A[x]]=1 ,DP[x][1-A[x]]=0;

2.定义Fx:穿过x的满足题目要求的最长节点数量，则Fx由以x为端点的最长链和次长链组成。

状态转移方程：
对(父亲x->孩子y A[x]为x的节点颜色)

①若A[x]=0：DP[x][0]=max(DP[x][0],DP[y][1]+1);

②若A[x]=1：DP[x][1]=max(DP[x][1],DP[y][0]+1);

在此基础上，Fx因为由最长和次长组成，因此需要在DP[x]更新前完成更新，因此：
①若A[x]=0

Fx=max(Fx,DP[x][0]+DP[y][1]);

DP[x][0]=max(DP[x][0],DP[y][1]+1);

②若A[x]=1;

Fx=max(Fx,DP[x][1]+DP[y][0]);

DP[x][1]=max(DP[x][1],DP[y][0]+1);

目标状态:Fx

参考代码

本站题目仅供学习，GESP版权归CCF所有，如有侵权请联系删除。站长陈老师QQ及微信:208234。