My algo is O(n * sqrt(n)) But i have WA on test 18. My solution gives same answers with brute force solution on my random tests. But what is 18-th test? Can anybody help me?

Maybe, arithmetic overflow? Some answers may not fit in the standard 32-bit integer types...

Really?
Yes, I use usual int instead __int64. But in problem statement Q <= 10^5 and V <= 10^4 for all I queryes. So all values on nodes is <= 10^5*10^4. It is less than 2^31-1. But... maybe I misuderstud anything?
BTW I will try submit with __int64 :)
Thank You!

Any more ideas?

It fits in 32 bit integers. (I got AC using long). I also used O(n * sqrt(n)) (teoretically) but I can't think why you get WA on test 18... there must be a mistake someware.

AC now!

here it is program that generated contrary test for my solution:

n = 10000;
printf( "%d\n", n );
  for  (i = 0;  i < n-1;  ++i)
  {
      printf( "%d %d\n", random(i+1)+1, i+2 );
  }
m = 1000;
printf( "\n%d\n", m );
k = random(m);
    for ( i = 0 ; i < k ; i++ )
        printf( "I %d %d\n", random(n) + 1, random(10001) );

    for ( i++ ; i < m ; i++ )
        printf( "G %d %d\n", random(n) + 1, random(n) + 1 );

How can solve this problem in O(N * sqrt(N)) ?? Is it simple to implement ?

My solution is O(N * log^2(N)). But it's very complex and slow ( 4.25s )

my program work about N*sqrt(N) but i have TL 17
any ideas about this test?

Can U tell me about ur method

this is my email oybek_all@yahoo.com

Edited by author 03.08.2008 14:40

help me, please!!  How solved? What algorithm? Tried through LCA and RSQ but could not....mail: Vashegin_roman@mail.ru

Build clusters of O(sqrt(N)) in size using DFS-inside-DFS. Outer clusters tree will have O(sqrt(N)) diameter. Optimize by skipping a cluster completely when you find a way. When you increase radiation level, enumerate all "downward portals" to other clusters passing through incremented node, and update their skip-values (maximal radiation level on the path from downward portal towards upward portal to parent cluster). Keep separate list of in-cluster edges. Although outer cluster tree's diameter is O(sqrt(N)), its size is still O(N) (there can be a lot of tiny leaf clusters). You don't want to enumerate all of them if you want to stay at O(sqrt(N)) during increments :)

Edited by author 09.09.2008 02:44

More simply:
Divide Tree in sqrt(N) layers and in clusters.
If cluster small jumping through layer when forming
answer on 'G' query, but renewing for verteces of this cluster information on each 'I' query.
If cluster big go through it by step by step but in this case renewing information only for one vertex in 'I' query.

why we have to use __int64?