codeforces 743D Chloe and pleasant prizes 트리 dp
4610 단어 트리codeforces
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Generous sponsors of the olympiad in which Chloe and Vladik took part allowed all the participants to choose a prize for them on their own. Christmas is coming, so sponsors decided to decorate the Christmas tree with their prizes.
They took n prizes for the contestants and wrote on each of them a unique id (integer from 1 to n). A gift i is characterized by integer ai — pleasantness of the gift. The pleasantness of the gift can be positive, negative or zero. Sponsors placed the gift 1on the top of the tree. All the other gifts hung on a rope tied to some other gift so that each gift hung on the first gift, possibly with a sequence of ropes and another gifts. Formally, the gifts formed a rooted tree with n vertices.
The prize-giving procedure goes in the following way: the participants come to the tree one after another, choose any of the remaining gifts and cut the rope this prize hang on. Note that all the ropes which were used to hang other prizes on the chosen one are not cut. So the contestant gets the chosen gift as well as the all the gifts that hang on it, possibly with a sequence of ropes and another gifts.
Our friends, Chloe and Vladik, shared the first place on the olympiad and they will choose prizes at the same time! To keep themselves from fighting, they decided to choose two different gifts so that the sets of the gifts that hang on them with a sequence of ropes and another gifts don't intersect. In other words, there shouldn't be any gift that hang both on the gift chosen by Chloe and on the gift chosen by Vladik. From all of the possible variants they will choose such pair of prizes that the sum of pleasantness of all the gifts that they will take after cutting the ropes is as large as possible.
Print the maximum sum of pleasantness that Vladik and Chloe can get. If it is impossible for them to choose the gifts without fighting, print Impossible.
Input
The first line contains a single integer n (1 ≤ n ≤ 2·105) — the number of gifts.
The next line contains n integers a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — the pleasantness of the gifts.
The next (n - 1) lines contain two numbers each. The i-th of these lines contains integers ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi) — the description of the tree's edges. It means that gifts with numbers ui and vi are connected to each other with a rope. The gifts' ids in the description of the ropes can be given in arbirtary order: vi hangs on ui or ui hangs on vi.
It is guaranteed that all the gifts hang on the first gift, possibly with a sequence of ropes and another gifts.
Output
If it is possible for Chloe and Vladik to choose prizes without fighting, print single integer — the maximum possible sum of pleasantness they can get together.
Otherwise print Impossible.
Examples
input
8
0 5 -1 4 3 2 6 5
1 2
2 4
2 5
1 3
3 6
6 7
6 8
output
25
input
4
1 -5 1 1
1 2
1 4
2 3
output
2
input
1
-1
output
Impossible
제목: 주어진 나무에 대해 각 노드에 권중이 있는데 어떻게 두 노드를 골라서 이 두 노드의 자수가 중합된 노드가 없고 그 자수의 권중의 합이 가장 크냐고 묻는다.
첫 번째 트리 dp의 제목;
사고방식: 이 제목은 모든 점이 1과 연결된다는 것을 알려주었다. 즉, 이 나무의 뿌리는 1이다. 나는 처음에 잎 노드에서 뿌리 노드까지 찾으려고 했는데,
이 점을 서브트리로 하는 모든 노드에 대해 그는 두 가지 가능한 값을 얻을 수 있다. 하나는 dp[i]이고, 하나는num[i]이다.dp[i]는 이 점을 뿌리로 하는 하위 트리의 값을 나타낸다
가장 큰num[i]는 이 점을 뿌리로 하는 하위 트리의 소유권 값(자신 포함)을 나타낸다.
우리가 두 개의 자수를 가장 크게 하려면, 이 점을 뿌리로 하는 자수 중에서 두 개와 가장 큰 것을 찾으면 된다
#include #include #include #include #include const int N=2e5+10; const int inf= 2*0x3f3f3f3f; using namespace std; long long num[N],dp[N],ans; vectorvt[N]; void dfs(int u,int f) { int i;for(i=0;i{ intv=vt[u][i];if(v==f)continue;dfs(v,u);num[u]+=num[v];if(dp[u]!=-inf)ans=max(ans,dp[u]+dp[v]);dp[u]=max(dp[u],dp[v]);} dp[u]=max(dp[u],num[u]); } int main() { int i,n; long long a,b; while(scanf("%d",&n)!=EOF) { ans=-inf; for(i=1;i<=n;i++) { vt[i].clear(); dp[i]=-inf;}for(i=1;i<=n;i++) scanf("%lld",&num[i]);for(i=1;i{ scanf("%lld %lld",&a,&b); vt[a].push_back(b); vt[b].push_back(a);}dfs(1,-1);if(ans!=-inf)printf("%lld",ans);elseprintf("Impossible"); } return 0; }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ] 2233번: 사과나무 (Java)~트리는 어렵다!!!!!!!!!!!!!!!!!~ 전체 로직 1. parent 배열과 root 배열 채우기 Stack을 이용하여 트리 만들기 이진 배열을 비교하며 삭제하고자 하는 노드의 '실제 인덱스' 구하기 2. 가...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.