学步园

对于一棵树而言，记录下包含此结点的最大num和不包含此节点的最大num，进行dp。

我发现自己每每写完一题，就再也不想多写一个字，以至于解题报告如同旧时的电报，惜字如金。

#include <cstdio><br /> #include <algorithm><br /> using namespace std;</p> <p>enum<br /> {<br /> SIZE = 500001,<br /> };</p> <p>struct Node<br /> {<br /> int p; // parent<br /> int u; // used son<br /> int v1; // ocupy itself<br /> int v0; // does not contain itself<br /> int state; // state, use or not use<br /> };<br /> Node Tree[SIZE];</p> <p>int Case, N;</p> <p>void proc ()<br /> {<br /> int i;<br /> for ( i = N; i >= 2; i -- )<br /> {<br /> Tree[i].v1 ++;<br /> int p = Tree[i].p;<br /> Tree[p].v1 += Tree[i].v0;<br /> int u = Tree[p].u;<br /> if ( u == -1 )<br /> {<br /> Tree[p].v0 += Tree[i].v1;<br /> Tree[p].u = i;<br /> }<br /> else<br /> {<br /> if ( Tree[u].v0 + Tree[i].v1 > Tree[i].v0 + Tree[u].v1 )<br /> {<br /> Tree[p].v0 += Tree[i].v1 - Tree[u].v1 + Tree[u].v0;<br /> Tree[p].u = i;<br /> }<br /> else<br /> Tree[p].v0 += Tree[i].v0;<br /> }<br /> }<br /> printf ( "%d/n", Tree[1].v0 * 1000 );<br /> Tree[1].state = 0;<br /> int f = 0;<br /> for ( i = 2; i <= N; i ++ )<br /> {<br /> int p = Tree[i].p, u = Tree[i].u;<br /> if ( Tree[p].state == 1 )<br /> {<br /> Tree[i].state = 0;<br /> }<br /> else<br /> {<br /> if ( Tree[p].u == i )<br /> Tree[i].state = 1;<br /> else<br /> Tree[i].state = 0;<br /> }<br /> if ( Tree[i].state == 0 )<br /> continue;<br /> if ( f ++ )<br /> printf ( " " );<br /> printf ( "%d", i );<br /> }<br /> printf ( "/n" );<br /> }</p> <p>void init ()<br /> {<br /> memset ( Tree, 0, sizeof ( Tree ) );<br /> scanf ( "%d", &N );<br /> int i, t;<br /> Tree[1].p = Tree[1].u = -1;<br /> for ( i = 2; i <= N; i ++ )<br /> {<br /> scanf ( "%d", &t );<br /> Tree[i].p = t;<br /> Tree[i].u = Tree[i].state = -1;<br /> }<br /> }</p> <p>int main ()<br /> {<br /> //freopen ( "in.txt", "r", stdin );<br /> scanf ( "%d", &Case );<br /> int i;<br /> for ( i = 0; i < Case; i ++ )<br /> {<br /> if ( i )<br /> printf ( "/n" );<br /> init ();<br /> proc ();<br /> }<br /> return 0;<br /> }