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 );

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