[五年级春季]第五讲：分解质因数[分析与解]
分解质因数
1、把一个合数分解成几个质数相乘的形式叫做分解质因数，这几个质数叫做这个合数的质因数。一般是用“短除法”逐级将一个合数分解质因数。
2、求一个合数的因数个数与所有因数的和的方法，是先把这个数分解质因数，再根据不同质因数的个数，用下面的公式计算。
自然数M分解质因数：M=Aa&Bb…&Ff。
则M的因数个数有：（a+1）&（b+1）&…&（f+1）个。
M所有因数的和：（A0+A1+…+Aa）&（B0+B1 +…+Bb）&……&（F0+F1+…+Ff）.
例1：把18个苹果平均分成若干份，每份大于1个，小于18个。一共有多少种不同的分法？
先把18分解质因数：18=2&3&3。可以看出：18的因数有1，2，3，6，9，18.除开1和18，还有4个因数，所以，一共有4种不同的方法。
【分析与解】方法一：平均分成若干份，则每份个数是18的因数。18的因数有多少个，就有多少种分法。因为18=21&32，18的因数有：（1+1）&（2+1）=6个。共有6种分法，因为要求每份大于1并小于18，所以去掉1和18两个因数。共有4种分法。
方法二：列举18的因数。18=1&18=2&9=1&18，有6个因数。除开1和18两种情况，还有4种分法。
有60个同学分成人数相等的小组去慰问解放军叔叔，每组不少于6人，不多于15人。有哪几种分法？
【分析与解】60为分成人数相等的人数，每组人数是60的因数，60的因数有多少个就有多少种分法。
①分解质因数：60=22&31&51；
②60的因数有：（2+1）&（1+1）&（1+1）=12个。
③除开：1，2，3，4，5和20，30，60八种情况。
④实际分法有：12-8=4种。
列举法：60=1&60=2&30=3&20=4&15=5&12=6&10，共有12个因数，只有6，10，12，15个因数符合条件，所以有4种分法。
答：有4种分法，分别是每组6人，10人，12人，15人。
例2：有4个学生，他们的年龄恰好是一个比一个大一岁，而他们的年龄的乘积是5040.他们的年龄是多少？
思路点拨：根据题意，4个学生年龄乘积是5040，则每个学生年龄都是5040的因数，四位学生年龄的全部质因数正好是5040的质因数。我们先把5040分解质因数，再把质因数进行组合成四个连续自然数就行了。
①分解质因数：5040=24&32&51&71；
②组合成连续自然数：因为质因数中没有11，所以四个自然数应该比11小，其中应该有7.
则可以组成，5040=71&23&32&（21&51）=7&8&9&10；
答：他们的年龄分别是7岁，8岁，9岁，10岁。
有5个孩子，他们的年龄一个比一个小1岁，他们的年龄的乘积是55440.求这5个孩子的年龄各是多少？
【分析与解】根据题意，5个学生年龄乘积是55440，则每个学生年龄都是55440的因数，五位学生年龄的全部质因数正好是55440的质因数。我们先把55440分解质因数，再把质因数进行组合成五个连续自然数就行了。
①分解质因数：55440=24&32&51&71&111；
②组合成连续自然数：因为质因数中最大是11，而没有13，所以五个自然数应该比13小，其中应该有11和7.
则可以组成，55440=71&23&32&（21&51）&111=7&8&9&10&11；
答：他们的年龄分别是7岁，8岁，9岁，10岁和11岁。
例3：下面的算式里，囗里数字各不相同，求这四个数字的和。
囗囗&囗囗=1995
思路点拨：要使两个两位数的积是1995.那么，这两个数的积应和1995有相同的质因数。1995=3&5&7&19，可以有35&57=1995和21&95=1995。因为要满足“数字各不相同”的条件，所以取21&95=1995，这四个数字的和是：2+1+9+5=17。
①分解质因数：1995=31&51&71&191；
②组合质因数成两位数相乘：1995=（31&71）&（51&191）=21&95
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
=（31&191）&（51&71）=57&35，数学有重复，排除。
③四个数字的和：2+1+9+5=17.&&
答：这四个数字的和是17.
如果囗囗&囗囗=2009，那么，这两个两位数的和是&&&&&&
。【2009年成外嘉祥外国语学校择校题】
【分析与解】①分解质因数：2009=72&411；
②组合质因数成两位数相乘：2009=72&411=49&41
③两个数的和：49+41=90.&&
答：这两个两位数是90.
把下面各数写成质因数相乘的形式。
（1）255&&&&&&&&&&&&&&&&&&&&&
255==31&51&171；&&&&&&&&&&&&&&&&&&&&&
360==23&32&51。
2.小明是个中学生，他说：“这次考试，我的名次乘我的年龄再乘我的考试分数，结果是2910.”你能算出小明的名次、年龄与这次考试的成绩吗？
【分析与解】：根据题意，小明的名次、年龄与分数等3个数的乘积是2910，则这三个数都是2910的因数，且三个数的全部质因数正好组成2910的质因数。我们先把2910分解质因数，再把质因数进行组合成三个符合条件自然数就行了，即小明是个中学生，应该是十五岁左右，名次应该是一位数，分数应该在100以内。
①分解质因数：2910=21&31&51&971；
②组合成符合条件自然数：2910=21&（31&51）&971
小明的年龄应是3&5=15岁；考试分数应是97分，名次应该是第二名。
答：小明是第二名，今年15岁，这次考试得97分。
3.有两个数，已知其中一个数是另一个数的5倍，这两个数的积为3920，那么，这两个数分别是多少？
【分析与解】：根据题意，其中一个数是另一个数的5倍，它们的积就应该是一倍数的平方再乘5.可以用3920除以5后，再分解质因数，并组成完全平方数。
设较小的数为A，则较大数为5A，得：A&5A=3920
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&A2=(22&71) &(22&71)
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
A2=282&&&&&&&&
另一个数是：28&5=140.
答：这两个数分别是28和140.
4.两个质数的和是39，求这两个质数的积是多少？
【分析与解】：质+质=39，39为奇数，只有奇数+偶数=奇数，所以两个质数，必定有一个质数是偶数。而质数中只有2是偶数。所以这两个质数分别是2和37，它们的乘积：2&37=74。
5.三个自然数的乘积为84，其中两个数的和等于另一个数，这三个数分别是多少？
【分析与解】：①分解质因数:84=22&31&71；
②组合成三个数：84=22&31&71；且：22+31=71
答：这三个数分别是3，4和7.
有三个自然数a,b,c。若已知a&b=10,b&c=35,a&c=14，a&b&c的值是多少？
【分析与解】：根据a&b=10,b&c=35,a&c=14，我们将三个积连乘得：
a&b&b&c&a&c=10&14&35
a2&b2&c2= 22&52&72
a&b&c= 2&5&7
a&b&c= 70&&&
答：a&b&c的值是70.
7.王老师带领一班同学去植树，学生恰好分成4组。如果王老师和学生每人植树一样多，那么，他们一共植了539棵。这个班有多少学生？每人植树多少棵？
【分析与解】：从学生恰好分成4组，我们可知学生人数是4的倍数，王老师和学生一起植树，并且一样多。说明学生人数加1后，是539的因数。可以先分解539的质因数。再看哪一个因数比4的倍数多1，这个因数就是总人数。
①分解质因数：539= 72&111
②观察质因数，组成比4的倍数多1的有49和77，根据539=49&11=7&77。得总人数有二种可能：
一是49人，则学生人数是：49-1=48人，每人植树11棵。
二是77人，则学生人数是：77-1=76人，每人植树7棵。
答：这个班有48名或76名学生，每人植树11棵或7棵。
答：这个班有学生48人或76人，每人植树11棵或7棵。
8. 小明家的电话号码是七位数，它恰好是八个连续质数的乘积，这个积的末四位数是前三位数的10倍，小明家的电话是多少？
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。codeforces（12）
苟蒻太懒了。。现在才写
memory limit per test
256 megabytes
standard input
standard output
Dante is engaged in a fight with &The Savior&. Before he can fight it with his sword, he needs to break its shields. He has two guns, Ebony and Ivory, each of them is able to perform any non-negative number of shots.
For every bullet that hits the shield, Ebony deals&&units of damage while Ivory deals&&units
of damage. In order to break the shield Dante has to deal&exactly&&units
of damage. Find out if this is possible.
The first line of the input contains three integers&,&,&&()&—
the number of units of damage dealt by Ebony gun and Ivory gun, and the total number of damage required to break the shield, respectively.
Print &Yes& (without quotes) if Dante can deal exactly&&damage
to the shield and &No& (without quotes) otherwise.
In the second sample, Dante can fire&&bullet from Ebony and&&from
Ivory to deal exactly&&damage. In the third sample, Dante can fire&&bullet
from ebony and no bullets from ivory to do&&damage.
但丁用黑檀木和白象牙攻击，黑檀木每次射击造成a点伤害，而白象牙b点，但丁必须造成精确的x点伤害才能击败怪兽，问能否造成？
心爱的鬼泣。。帅气的但丁
一维背包判断存在性，不多提
#include&iostream&
#include&cstdio&
#include&cstdlib&
#include&algorithm&
#include&cstring&
#include&cmath&
#include&vector&
#include&queue&
const int maxn = 1E4 + 10;
int f[maxn],a,b,c;
int main()
#ifdef YZY
freopen(&yzy.txt&,&r&,stdin);
cin && a && b &&
for (int i = i &= i++)
if (f[i-a])
for (int i = i &= i++)
if (f[i-b])
if (f[c]) printf(&Yes&);
else printf(&No&);
memory limit per test
256 megabytes
standard input
standard output
Mr. Santa asks all the great programmers of the world to solve a trivial problem. He gives them an integer&&and asks for the number
of positive integers&, such that the factorial of&&ends
with exactly&&zeroes. Are you among those great programmers who can solve this problem?
The only line of input contains an integer&&()&—
the required number of trailing zeroes in factorial.
First print&&— the number of values of&&such
that the factorial of&&ends with&&zeroes.
Then print these&&integers in increasing order.
The factorial of&&is equal to the product of all integers from&&to&&inclusive,
In the first sample,&,&,&,&&and&.
给出整数n，问有多少个数的阶乘，刚好有n个后缀0
2*5 = 10有一个0不多说，当数字逐渐增大，其分解质因数后含有的2数量必远远大于5，所以统计5的个数即可
#include&iostream&
#include&cstdio&
#include&cstdlib&
#include&algorithm&
#include&cstring&
#include&cmath&
#include&vector&
#include&queue&
const int maxn = 1E5 + 10;
int ans[maxn],tot,m;
int main()
#ifdef YZY
freopen(&yzy.txt&,&r&,stdin);
int sum = 0;
for(int i = 5; ; i++) {
while (k % 5 == 0) k/=5,++
if (tot == m) ans[++sum] =
if (tot & m)
printf(&%d\n&,sum);
for (int i = 1; i &= i++) printf(&%d &,ans[i]);
memory limit per test
256 megabytes
standard input
standard output
After observing the results of Spy Syndrome, Yash realised the errors of his ways. He now believes that a super spy such as Siddhant can't use a cipher as basic and ancient as Caesar cipher. After many weeks of observation of Siddhant’s sentences, Yash determined
a new cipher technique.
For a given sentence, the cipher is processed as:
For example, when this cipher is applied to the sentence
Kira is childish and he hates losing
the resulting string is
ariksihsidlihcdnaehsetahgnisol
Now Yash is given some ciphered string and a list of words. Help him to find out any original sentence composed using only words from the list. Note, that any of the given words could be used in the sentence multiple times.
The first line of the input contains a single integer&&()&—
the length of the ciphered text. The second line consists of&lowercase English letters&— the ciphered text&.
The third line contains a single integer&&()&—
the number of words which will be considered while deciphering the text. Each of the next&&lines contains a non-empty word&&(| ≤ 1 000)
consisting of uppercase and lowercase English letters only. It's guaranteed that the total length of all words doesn't exceed&.
Print one line — the original sentence. It is guaranteed that at least one solution exists. If there are multiple solutions, you may output any of those.
ariksihsidlihcdnaehsetahgnisol
Kira is childish and he hates losing
iherehtolleh
HI there HeLLo
In sample case 2 there may be multiple accepted outputs, &HI there HeLLo& and &HI there hello& you may output any of them.
Yash对自己的一段话加密：
1.将所有大写字母转成小写
2.将每个单词翻转
3.去除所有空格
现给出这段话中可能出现的一些单词，问这段话的原话是什么？
若有多种解输出任意一种
注意到单词数不超过1000000，考虑建立一棵trie
原话字符&=10000，那么从左到右for一遍尝试找解，又字符长度&=1000所以每个位置的查询向左1000位即可。tri可以以小写字符存储，找到存在的单词点输出对应位置原单词，降低编写难度
#include&iostream&
#include&cstdio&
#include&cstdlib&
#include&algorithm&
#include&cstring&
#include&cmath&
#include&vector&
#include&queue&
const int maxn = 1E4 + 10;
int ch[26];
memset(ch,0,sizeof(ch));
}t[1000010];
int cnt,n,m,f[maxn],last[maxn];
char x[maxn],y[1010];
vector &char& v[maxn*10];
void Insert(int o,int pos,int len,int num)
for (; pos & pos++) {
if (y[pos] &= 'a') to = y[pos]-'a';
else to = y[pos]-'A';
if (!t[o].ch[to]) t[o].ch[to] = ++
o = t[o].ch[to];
t[o].END =
void solve(int pos)
int END = max(1,pos-999);
int o = 0;
for (int i = i &= END; i--) {
o = t[o].ch[x[i]-'a'];
if ((f[i-1] || i == 1) && t[o].END) {
last[pos] =
f[pos] = t[o].END;
void pri(int pos)
if (last[pos] != 1) pri(last[pos]-1);
int len = v[f[pos]].size();
for (int i = 0; i & i++) printf(&%c&,v[f[pos]][i]);
printf(& &);
int main()
#ifdef YZY
freopen(&yzy.txt&,&r&,stdin);
scanf(&%s&,1+x);
for (int i = 1; i &= i++) {
scanf(&%s&,&y);
int len = strlen(y);
Insert(0,0,len,i);
for (int j = 0; j & j++) v[i].push_back(y[j]);
for (int i = 1; i &= i++)
memory limit per test
512 megabytes
standard input
standard output
Yash has recently learnt about the Fibonacci sequence and is very excited about it. He calls a sequence Fibonacci-ish if
You are given some sequence of integers&, a2, ..., an.
Your task is rearrange elements of this sequence in such a way that its longest possible prefix is Fibonacci-ish sequence.
The first line of the input contains a single integer&&()&—
the length of the sequence&.
The second line contains&&integers&, a2, ..., an&(| ≤ 109).
Print the length of the longest possible Fibonacci-ish prefix of the given sequence after rearrangement.
28 35 7 14 21
In the first sample, if we rearrange elements of the sequence as&,&,&,
the whole sequence&&would
be Fibonacci-ish.
In the second sample, the optimal way to rearrange elements is&,&,&,&,&.
现有一个数组，从中任意选一些数构成一个斐波那契数列，问能够成的最长数列的长度是多少
一堆绝对值&=10^9的数用来构造斐波那契数列，虽然斐波那契数列增长不快，但是长度也不可能超过100，暴力枚举最开始的两个数，尝试能否构成即可
用离散化存数的时候一开始没考虑到 f0 = f1的情形
#include&iostream&
#include&cstdio&
#include&cstdlib&
#include&algorithm&
#include&cstring&
#include&cmath&
#include&vector&
#include&queue&
const int maxn = 1E3 + 10;
typedef long long LL;
int n,cur = 1,ans = 2,num[maxn],a[maxn],f[maxn],now[maxn];
void solve(int a,int b)
int tot = 2;
for (int i = 1; i &= i++) now[i] = 0;
++now[a]; ++now[b];
a = num[a]; b = num[b];
for (;;) {
LL x = 1LL*a+1LL*b;
if (x & - || x & )
int c = a+b;
int pos = lower_bound(num+1,num+cur+1,c)-
if (num[pos] != c || f[pos] == now[pos])
++ ++now[pos];
ans = max(ans,tot);
int main()
#ifdef YZY
freopen(&yzy.txt&,&r&,stdin);
for (int i = 1; i &= i++) {
scanf(&%d&,&a[i]);
num[i] = a[i];
sort(num+1,num+n+1);
for (int i = 2; i &= i++)
if (num[i] != num[i-1])
num[++cur] = num[i];
for (int i = 1; i &= i++)
for (int j = 1; j &= j++)
if (num[i] == a[j])
for (int i = 1; i &= i++)
for (int j = 1; j &= j++)
if (i != j || f[i] & 1)
solve(i,j);
memory limit per test
256 megabytes
standard input
standard output
An e-commerce startup pitches to the investors to get funding. They have been functional for&&weeks now and also have a website!
For each week they know the number of unique visitors during this week&&and
the revenue&.
To evaluate the potential of the startup at some range of weeks from&&to&&inclusive
investors use the minimum among the maximum number of visitors multiplied by&&and the minimum revenue during this period, that is:
The truth is that investors have no idea how to efficiently evaluate the startup, so they are going to pick some&&random distinct weeks&and
give them to managers of the startup. For each&&they
should pick some& ≥ li&and
report maximum number of visitors and minimum revenue during this period.
Then, investors will calculate the potential of the startup for each of these ranges and take minimum value of&, ri)&as
the total evaluation grade of the startup. Assuming that managers of the startup always report the optimal values of&&for
some particular&,
i.e., the value such that the resulting grade of the startup is maximized, what is the expected resulting grade of the startup?
The first line of the input contains two integers&&and&&().
The second line contains&&integers&&( ≤ 107)&—
the number of unique visitors during each week.
The third line contains&&integers&&( ≤ 107)&—the
revenue for each week.
Print a single real value&— the expected grade of the startup. Your answer will be considered correct if its absolute or relative error does not exceed&.
Namely: let's assume that your answer is&, and the answer of the jury is&.
The checker program will consider your answer correct, if&.
300 200 300
133.3333333
Consider the first sample.
If the investors ask for& = 1&onwards,
startup will choose& = 1,
such that max number of visitors is&&and minimum revenue is&.
Thus, potential in this case is&.
If the investors ask for& = 2&onwards,
startup will choose& = 3,
such that max number of visitors is&&and minimum revenue is&.
Thus, potential in this case is&.
If the investors ask for& = 3&onwards,
startup will choose& = 3,
such that max number of visitors is&&and minimum revenue is&.
Thus, potential in this case is&.
We have to choose a set of size&&equi-probably and take minimum of each. The possible sets here are :,,,
effectively the set of possible values as perceived by investors equi-probably:. Thus, the expected value is&.
现有两个数组v,c
对于每个l，找到合适的r使得p(l,r)的值最大
这样得到n个数，现在从中任选k个数组成一个可重集合，取集合最小的数作为这个集合的值，问这些值的期望值是多少？
对于确定l找r：
随着r的增加100*max vk是个增函数，min ck是个减函数，既然p(l,r)是取两者中的最小值，显
然两函数交点符合。由于交点不一定存在，所以最优解可能是左边一个或是右边一个。于是可以二
分，每个r用RMQ得到当前的v和c函数，判断c是否&v即可
我们得到了n个数，c(n,k)却巨大，连算出这个除数都难以保留。考虑将这n个数从小到大排序，如果第i个数是它所在集合的值，那么必定在[i+1,n]中找其余的k-1个数，于是
ans = ∑a[i]*c(n-i,k-1)/c(n,k)
又n*c(n-1,m-1) = m*c(n,m)
且c(n,m+1) = c(n,m)*(n-m)/m
通过这两个式子求解
O(nlogn) 二分、RMQ预处理复杂度，通过预处理RMQ区间长对应的log使RMQ查询复杂度为O(1)
一开始v函数没乘以100，数据强转类型没注意。。。
#include&iostream&
#include&cstdio&
#include&queue&
#include&algorithm&
typedef double DB;
const int maxn = 1E6 + 10;
int n,a[maxn][20],b[maxn][20],c[maxn],LOG[maxn];
bool Judge(int l,int r)
int len = LOG[r-l+1];
int A = 100*max(a[l][len],a[r-(1&&len)+1][len]);
int B = min(b[l][len],b[r-(1&&len)+1][len]);
return A&B;
int main()
#ifdef YZY
freopen(&yzy.txt&,&r&,stdin);
cin && n &&
for (int i = 1; i &= i++) scanf(&%d&,&a[i][0]);
for (int i = 1; i &= i++) scanf(&%d&,&b[i][0]);
for (int j = 1; j & 20; j++)
for (int i = 1; i &= i++) {
if (i + (1&&j-1) & n)
a[i][j] = max(a[i][j-1],a[i+(1&&(j-1))][j-1]);
b[i][j] = min(b[i][j-1],b[i+(1&&(j-1))][j-1]);
int now = 0,sum = 1;
for (int i = 1; i &= i++) {
if (sum &= i) LOG[i] = now-1;
sum &&= 1;
LOG[i] = now-1;
LOG[1] = 0;
for (int i = 1; i &= i++) {
int L,R; L = R =
while (R - L & 1) {
int mid = (L+R) && 1;
if (Judge(i,mid)) L =
int len = LOG[L - i + 1];
int A = 100*max(a[i][len],a[L-(1&&len)+1][len]);
int B = min(b[i][len],b[L-(1&&len)+1][len]);
c[i] = min(A,B);
len = LOG[R - i + 1];
A = 100*max(a[i][len],a[R-(1&&len)+1][len]);
B = min(b[i][len],b[R-(1&&len)+1][len]);
c[i] = max(c[i],min(A,B));
sort(c+1,c+n+1);
DB ans = 0;
DB N = n-1; DB M = k-1;
DB v = (DB)(k)/(DB)(n);
for (int i = 1; i &= i++) {
if (n - i & k - 1)
ans += v*(DB)(c[i]);
v = v/N*(N-M);
N -= 1.00;
printf(&%.10f&,ans);
memory limit per test
256 megabytes
standard input
standard output
Alice and Bob have a tree (undirected acyclic connected graph). There are&&chocolates
waiting to be picked up in the&-th vertex of the tree. First, they choose two different vertices as their starting positions (Alice
chooses first) and take all the chocolates contained in them.
Then, they alternate their moves, selecting one vertex at a time and collecting all chocolates from this node. To make things more interesting, they decided that one can select a vertex only if he/she selected a vertex adjacent to that one at his/her previous
turn and this vertex has not been already chosen by any of them during other move.
If at any moment one of them is not able to select the node that satisfy all the rules, he/she will skip his turns and let the other person pick chocolates as long as he/she can. This goes on until both of them cannot pick chocolates any further.
Due to their greed for chocolates, they want to collect as many chocolates as possible. However, as they are friends they only care about the total number of chocolates they obtain&together. What
is the maximum total number of chocolates they may pick?
The first line of the input contains the single integer&&(n)&—
the number of vertices in the tree.
The second line contains&&integers&&( ≤ 109),&-th
of these numbers stands for the number of chocolates stored at the node&.
Then follow&&lines that describe the tree. Each of them contains two integers&&and&&(, vi ≤ n)&—
indices of vertices connected by the&-th edge.
Print the number of chocolates Alice and Bob can collect together if they behave optimally.
1 2 3 4 5 6 7 8 9
In the first sample, Alice may start at the vertex&&and Bob at vertex&.
Alice will select vertex&&and Bob has no options now. Alice selects the vertex&&and
they both stop.
In the second sample, both of them will pick either of the nodes alternately.
有一棵树每个节点有a个巧克力，现有两个好朋友在这棵树上走，两个人走的路径不能有交叉，他们所过之处不留下一个巧克力，问最多能收集多少个
树上dp。。简直了
一条路径肯定是从某叶节点开始向上，走到某节点后往下走到无法走，称最高处节点为祖先
1.两条路径祖先也有公共祖先
记ma[i]为以i为根的子树的最大路径，这种情况的解决就变成最大值+次大值
2.两条路径用祖孙关系
大概都可以描述成这种图
对于一些点2，这些点不在答案中。
显然最优解的右下部是一个ma[x]+最高处祖先往下的一段
记t[i]来维护这个东西，显然一颗子树的t[i]一确定，往上再怎么走最优解都是由许多个t[i]产生
于是t[i] = max{t[child]+a[i]} or a[i] + sum[m1] + sum[m2]
其中，sum[i]代表从某叶子到i节点路径最大值，m1，m2就是sum[ch]中的最大、次大
于是答案的计算就可以变成枚举每一个ch，找到除sum[ch]外的m1，m2，
ans = max{sum[m1] + sum[m2] + ma[ch]} or max{sum[m1] + t[ch]}
因为标记未清0和long long的问题WA两发。。
#include&iostream&
#include&cstdio&
#include&cstring&
#include&vector&
#include&algorithm&
const int maxn = 1E5 + 10;
typedef long long LL;
int n,vis[maxn];
LL ans = 0,a[maxn],sum[maxn],ma[maxn],ml[maxn],mr[maxn],t[maxn],l[maxn],r[maxn];
vector &int& v[maxn],v1[maxn];
void dfs(int x)
for (int i = 0; i & v1[x].size(); i++) {
int to = v1[x][i];
if (vis[to])
vis[to] = 1;
v[x].push_back(to);
void solve(int k)
int siz = v[k].size();
if (!siz) {
sum[k] = ma[k] = t[k] = a[k];
LL m1,m2,M1,M2;
m1 = m2 = M1 = M2 = 0;
for (int i = 0; i & i++) {
int to = v[k][i];
solve(to);
if (ma[to] & M1) {
M2 = M1; M1 = ma[to];
else if (ma[to] & M2) M2 = ma[to];
if (sum[to] & m1) {
m2 = m1; m1 = sum[to];
else if (sum[to] & m2) m2 = sum[to];
ma[k] = max(ma[k],ma[to]);
t[k] = max(t[k],t[to] + a[k]);
ma[k] = max(ma[k],a[k]+m1+m2);
sum[k] = m1+a[k];
for (int i = 0; i & i++)
l[i+1] = r[i+1] = sum[v[k][i]];
l[0] = r[siz+1] = ml[0] = mr[siz+1] = 0;
ans = max(ans,1LL*M1+1LL*M2);
for (int i = 1; i &= i++) {
if (l[i] & l[i-1]) ml[i] = l[i-1];
else if (l[i] & ml[i-1]) {
ml[i] = l[i]; l[i] = l[i-1];
else l[i] = l[i-1],ml[i] = ml[i-1];
for (int i = i--) {
if (r[i] & r[i+1]) mr[i] = r[i+1];
else if (r[i] & mr[i+1]) {
mr[i] = r[i]; r[i] = r[i+1];
else r[i] = r[i+1],mr[i] = mr[i+1];
for (int i = 0; i & i++) {
LL now[4];
int ch = v[k][i];
now[0] = l[i]; now[1] = ml[i];
now[2] = r[i+2]; now[3] = mr[i+2];
sort(now,now+4);
ans = max(ans,a[k] + now[2] + now[3] + ma[ch]);
ans = max(ans,t[ch] + now[3] + a[k]);
t[k] = max(t[k],ma[ch] + now[3] + a[k]);
int main()
#ifdef YZY
freopen(&yzy.txt&,&r&,stdin);
for (int i = 1; i &= i++) scanf(&%I64d&,&a[i]);
for (int i = 1; i & i++) {
int x,y; scanf(&%d%d&,&x,&y);
v1[x].push_back(y);
v1[y].push_back(x);
vis[1] = 1; dfs(1);
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：9446次
积分：1540
积分：1540
排名：第18684名
原创：146篇
(3)(24)(20)(12)(9)(9)(19)(7)(6)(2)(29)(10)(2)