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

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.

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