#include <bits/stdc++.h>
using namespace std;
int tik = 1;
int ans;
int a[100005];
int tin[100005];
int tout[100005];
vector <int> g[100005];
vector <int> diff[100005];
int n , m , root;
bool is( int b , int a ) // return b is son of a
{
return ( tin[a] <= tin[b] && tout[a] >= tout[b] );
}
void dfs( int v , int p = -1 )
{
tin[v] = tik++;
for(auto to : g[v])
{
if( to == p )continue;
dfs( to , v );
}
tout[v] = tik++;
}
void rec( int v , int sum = 0 , int ost = m - 1)
{
if( ost == 0 )
{
ans = max( ans , sum );
return;
}
for(auto to : diff[v])
{
rec( to , sum + a[to], ost - 1 );
}
}
main()
{
//freopen("d.in" , "r" , stdin);
//freopen("d.out" , "w" , stdout);
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
int p , cost;
cin >> p >> cost;
a[i] = cost;
if( p == 0 )
{
root = i;
continue;
}
g[p].push_back( i );
g[i].push_back( p );
}
dfs( root );
for(int son = 1; son <= n; son++)
{
for(int i = son; i <= n; i++)
{
if( !is( son , i ) && !is( i , son ) )
{
diff[son].push_back( i );
}
}
}
for(int i = 1; i <= n; i++)
rec( i , a[i] );
cout << ans;
}
Compilation message
biochips.cpp:51:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
