程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> ASC(1)C(樹形DP)

ASC(1)C(樹形DP)

編輯:關於C語言

ASC(1)C(樹形DP)


New Year Bonus Grant

Special JudgeTime Limit: 6000/3000MS (Java/Others)Memory Limit: 128000/64000KB (Java/Others) SubmitStatisticNext Problem

Problem Description

All programmers of Mocrosoft software company are organized in a strict subordination hierarchy. Every programmer has exactly one chief, except Bill Hates who is also the head of the company and has no chief.
Due to the celebration of the new 2003 year, chief accountant of Mocrosoft decided to pay a New Year Bonus Grant of 1000 dollars to some programmers. However being extremely concerned of the company wealth she would like to designate the least possible amount of money for these grants. On the other hand she didn’t want to be accused of being too greedy or of giving preferences to some programmers. To do this, she developed the following scheme of grants appointment:
? Each programmer may either assign a grant to one of his subordinates or have a grant assigned to him by his chief or none of the above.
? No programmer can simultaneously receive a grant and assign a grant to one of his subordinates.
? No programmer can assign a grant to more than one of his subordinates
The scheme seemed to be designed perfectly — nobody would like to assign a grant to anybody since in this case he himself would not receive money. But programmers somehow discovered the plan of chief accountant and decided to make a trick to get the most money possible and share them fairly afterwards. The idea was to make such grant assignments that the total amount of grant money received is maximum possible.
You were selected to write the program which will find the optimal grants appointment.

Input

The first line of the input file contains integer N — the number of programmers in Mocrosoft company (2 ≤ N ≤ 500 000). Each programmer is assigned his unique identifier — integer number ranging from 1 to N . Bill Hates has number 1 and each programmer has the number greater then the number of his chief. The second line of the input file contains N ? 1 integers, i-th of which being the number of the chief of the worker whose number is (i + 1).

Output

On the first line of the output file print the maximum possible amount of money workers can get. On the second line output the numbers of programmers that will receive grant in ascending order.

Sample Input

4
1 1 2

Sample Output

2000
3 4

題意:給了一棵樹,求出最大的匹配,每個點要麼與父親匹配,要麼與一個孩子匹配,要麼不匹配
思路:n=500000,二分圖匹配算法顯然不能做
因為是一棵樹,果斷可以樹形DP
dp[u][0]表示該點不與父親匹配,其子樹的最大匹配數
dp[u][1]表示該點與其父親匹配,其子樹的最大匹配數
轉移很容易想到,dp[u][1]只能由dp[v][0]累加得到,其中v為u的孩子,因為u與其父親匹配以後就不能再與任何孩子匹配
dp[u][0]可以初始化為dp[u][1]表示u即不與父親匹配也不與孩子匹配
然後再用dp[v][1]去最大化dp[u][0]
最後還要求輸出具體方案,直接按樹的層次打印路徑即可

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved