首页 > 试题广场 >

最长树链

[编程题]最长树链
  • 热度指数：108 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
树链是指树里的一条路径。美团外卖的形象代言人袋鼠先生最近在研究一个特殊的最长树链问题。现在树中的每个点都有一个正整数值，他想在树中找出最长的树链，使得这条树链上所有对应点的值的最大公约数大于1。请求出这条树链的长度。

输入描述:
第1行：整数n（1 ≤ n ≤ 100000），表示点的个数。
第2~n行：每行两个整数x，y表示xy之间有边，数据保证给出的是一棵树。
第n+1行：n个整数，依次表示点1~n对应的权值（1 ≤ 权值 ≤ 1,000,000,000）。


输出描述:
满足最长路径的长度
示例1

输入

4
1 2
1 3
2 4
6 4 5 2

输出

3
算法知识视频讲解
开通博客
头像 shyyhs
发表于 2021-01-11 14:42:04
前言: 之前那个博客有大问题...确实是数据太水了. 思路: 首先我们处理出4e4以内的质数,然后因为任何合数都可以写成的形式,显然大于4e4的数,假如经过这么一次筛选,一定是不会出现超过4e4的合数.对于每个数,我们处理出来它们的质因子,这里呢,用的是最原始的判断方法,假如有n个数是大质数,那么就 展开全文
去ta的博客 赞 (5) 回复(1) 收起
头像 MYCui_
发表于 2021-01-13 17:33:23
前置知识： 素数判断（ 素数探测可用可不用吧） + + 分组思维 具体做法 观察题目，发现题目要求我们求 不等于 的一条最长链。 那么如果这条链上所有的节点的 都不为 ，那么它们肯定有着至少一个相同的质因子。 所以我们考虑将拥有相同质因子的节点放在一起处理，然后对于具有相同质因子的节点中求 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 sunrise__sunrise
发表于 2021-01-13 21:11:45
题目描述 给你个节点的一棵树，还有每个点的点权值，现在要你选出一条最长的边，保证这条边中全部的点之后的值不等于，也就是存在一个公共的因子全部点都有。 Solution 思路参考喵渺淼妙的死忠粉大佬这是原题解传送门观察到这个问题，那么我们第一步想想能不能去枚举，根据唯一分解定理，每一个数都可以拆成一堆 展开全文
去ta的博客 赞 (1) 回复(3) 收起
头像 WuliWuliiii
发表于 2021-01-16 22:33:18
很容易想到正确的解法，首先，我们可以知道（2 * 3 * 5 * 7 * 11 * 13 * ……）最多19个质数相乘就会达到1e9级别的。于是，我们可以考虑质数，我们可以知道一个数最多就是分成20个质数，所以我们直接进行对质数的检验会好一些。但是有些大质数应该怎么办呢？于是就有了米勒罗宾检验素数。 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 熠丶
发表于 2021-01-12 13:41:44
因为我太菜了，于是乎就找了份代码，理解了一下思路（把坑填完才能好好复习zz 思路： 1.先用筛求质数表,表长大约是sqrt(1e9) 2.建树 3.对权值进行质因数分解，并把对应的权值下标与素数对应起来存下来 4.然后树形dp求符合条件的最长链 代码 #include<bits/stdc+ 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 ⊙__⊙
发表于 2021-01-14 10:21:21
题意: 给出一颗树，请你找出最长的一条链，这条链上所有数值的GCD要大于1.并输出最长链的长度。 这题参考了 小熠小熠很不容易 大佬的思路。 思路就是，先建一棵树，然后从根开始搜索，这里要注意根不一定是1,要自己找根。 然后再搜索的时候，每次计算下GCD，如果GCD大于1，那么是满足条件的 展开全文
去ta的博客 赞 (0) 回复(1) 收起

问题信息

C++工程师 golang工程师 2017 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 c#工程师 美团 测试开发工程师 大数据开发工程师 树 Java工程师
来自：CodeM 2017美...
难度：
2条回答 3767浏览

热门推荐

通过挑战的用户

相关试题

最长树链

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号