7 5
1 2 20
2 5 100
2 3 20
6 3 70
4 1 10
3 7 5

Answer: 220

Edited by author 21.04.2022 19:37

Any thoughts whats in test #8? Solution passes all the tests here on forum and a lot of my tests. Just can't figure out what is wrong...

0) AC solve is DP on tree.
1) In DP inf = 1e9.
2) All test in the forum:

5 5
3 1 1
4 1 10
2 3 20
3 5 20
ans = 21

7 4
1 2 10
1 3 20
2 4 30
2 5 0
3 6 0
3 7 40
ans = 100

4 1
1 2 1
1 3 2
2 4 3
ans = 2

5 1
1 2 1
1 5 0
2 3 0
2 4 0
ans = 1

7 3
1 2 1
1 3 39
2 4 40
2 5 40
3 6 39
3 7 39
ans = 117

5 2
1 3 1
1 4 10
2 3 20
3 5 20
ans = 21

Edited by author 12.05.2008 19:54

Just like what I have said,I got a TLE and execution time is 1.029.
Who can help me?

I got TL#6.

After that just a little bit updated my solution:

int max( int pos, int len )
{
..if ( ch[pos][len] )
....return dp[pos][len];
---
....ch[pos][len] = 1;
....dp[pos][len] = res;
....return res;
---
}

and got AC in 0.015s.

Edited by author 23.03.2010 20:30

6 4
1 2 20
2 5 100
2 3 20
6 3 70
4 1 10

by the way : before you　use the dynamic programming on the tree structure, be sure you have build the tree correctly. That's why I got WA.

Source Code is available at :
ecnu_zp@yahoo.cn

Hello! Can somebody tell me if there is a faster algo than O(Q^2*N)? My algo works pretty fast, but I wondered if there is a better way to do it.

If I delete a branch, does it means that I delete also its sub-braches?

Cámara Chuy tienes que alcanzarme, este problema está bien bueno!

If your algo is correct, then maybe the problem is the way you build the tree.

Try this test:

5 2
3 1 1
4 1 10
2 3 20
3 5 20

Hope this test can help you.

i have a test:
5 2
1 2 1
1 4 20
1 5 20
2 3 10
i think answer is 21 but my AC code answer is 40
maybe i wrong???

Hi, guys!
Can't move throw #11 test. Need help.
I just have build tree, and in every step removing smallest leaf.
At last, I count sum of left leaf's weight and print it.
But, algorithm don't pass at #11 test.
Thanks

Can anyone please tell me what is test case #5....My code is giving the correct ans for all the tests in the forum..

can anyone please explain what test case 5 is  i have tried many times but iam not able to pass it

here it is:
4 1
1 2 1
1 3 2
2 4 3

Your answer can be 1 but it must be 2.

ans = 2;

Edited by author 21.10.2013 22:17

I guess there is a test case that the condition 1<=Q<=N-1 is not satisfied.
I put a condition that if Q is outside the given interval then output 0 and got WA#1.
Without this condition, it gives WA#8.

Edited by author 18.04.2013 20:01

# include <stdio.h>
# include <algorithm>

using namespace std;

struct daw
{
    long long rg,lf,nd,vl,mx;
};

long long a,b;

long long w[409];
long long c[409][5];
long long v[409][409];

daw d[409];

void btr(long long x)
{
    if(d[x*2+1].vl!=0)
    btr(x*2+1);

    if(d[x*2+2].vl!=0)
    btr(x*2+2);

    if(x!=0)
    d[(x-1)/2].nd=d[(x-1)/2].nd+d[x].nd+1;
}

long long dp(long long x, long long y)
{
//    prlong longf("%d %d",x,y);getchar();

    if(y==0)
    return 0;

    if(v[x][y]>0)
    return v[x][y];

    for(long long i=0;i<=y;i++)
    if(d[x].nd-d[x*2+2].nd>=i && d[x*2+1].vl>0 && d[x*2+2].vl>0)
    {
        long long q=0;

        if(i!=0)
        q+=d[x].lf;

        if(i!=y)
        q+=d[x].rg;

        if(i==0)
        v[x][y]=max(v[x][y],dp(x*2+2,y-1)+q);

        else if(i==y)
        v[x][y]=max(v[x][y],dp(x*2+1,y-1)+q);

        else
        v[x][y]=max(v[x][y],dp(x*2+1,i-1)+dp(x*2+2,y-i-1)+q);
    }

    return v[x][y];
}

int main()
{
    scanf("%lld %lld",&a,&b);

    for(long long i=0;i<a-1;i++)
    scanf("%lld %lld %lld",&c[i][0],&c[i][1],&c[i][2]);

    d[0].vl=1;
    w[1]=1;

    for(long long i=0;i<a-1;i++)
    for(long long j=0;j<a-1;j++)
    {
        if(d[i].vl==c[j][0] && w[c[j][1]]==0)
        {
            if(d[i*2+1].vl==0)
            {d[i].lf=c[j][2];  d[i*2+1].vl=c[j][1];}

            else
            {d[i].rg=c[j][2];  d[i*2+2].vl=c[j][1];}

            w[c[j][0]]=1;
        }

        if(d[i].vl==c[j][1] && w[c[j][0]]==0)
        {
            if(d[i*2+1].vl==0)
            {d[i].lf=c[j][2];  d[i*2+1].vl=c[j][0];}

            else
            {d[i].rg=c[j][2];  d[i*2+2].vl=c[j][0];}

            w[c[j][0]]=1;
        }
    }

    btr(0);

    if(b==1)
    {printf("%lld",max(d[0].rg,d[0].lf));return 0;}

    printf("%lld",dp(0,b));

    getchar();
    getchar();
}


Thanks

found my mistake


Edited by author 26.06.2012 01:56

First move apples to point...
like the sample :
5 2
1 3 1
1 4 10
2 3 20
3 5 20
apple[3]=1 , apple[4]=10 , apple[2]=10 , apple[5]=10..

dp [ f ] [ j + i ] = Max( dp [ f ] [ j + 1 ] ,dp [ f ] [ j ] + dp [ h ] [ i ] +apple [ h ] )

dp [ k ] [ i ] means k is a tree's root,it has i lines..gets the max value...
" f " is h's father...just like this...from leaf to root to update the value..
in the end,print the answer: dp [ 1 ] [ q + 1 ]


Edited by author 25.09.2011 10:11