{$M 64000000}
program MiameRishio;
const
        maxn                            = 10000;
        maxm                            = maxn shl 1;
        maxlg                           = 17;
        maxtree                         = maxn * 8;
        maxst                           = maxn * 2;
        maxvalue                        = maxlongint;
type
        edgetype                        = record
                                            go , pre , len : longint;
                                          end;
        treetype                        = record
                                            sign         : boolean;
                                            max , min    : longint;
                                            left , right : longint;
                                          end;
var
        test , n , e , stsize , po      : longint;
        tree1 , tree2                   : longint;
        last , depth , sum              : array [ 1..maxn ] of longint;
        get , go , fa2 , treeroot       : array [ 1..maxn ] of longint;
        len                             : array [ 0..maxn ] of longint;
        sa_st , sa_point , sa_edge , fa : array [ 0..maxn ] of longint;
        treeposi , treefirst , size     : array [ 1..maxn ] of longint;
        treebelong                      : array [ 0..maxn ] of longint;
        st , lg                         : array [ 1..maxst ] of longint;
        visited                         : array [ 1..maxst ] of boolean;
        edge                            : array [ 0..maxm ] of edgetype;
        tree                            : array [ 0..maxtree ] of treetype;
        f                               : array [ 0..maxlg , 1..maxst ] of longint;

procedure add_edge ( t1 , t2 , t3 : longint );
begin
  inc ( e );
  edge [ e ] . go := t2;
  edge [ e ] . pre := last [ t1 ];
  edge [ e ] . len := t3;
  last [ t1 ] := e;
  inc ( e );
  edge [ e ] . go := t1;
  edge [ e ] . pre := last [ t2 ];
  edge [ e ] . len := t3;
  last [ t2 ] := e;
end;

function fmax ( a , b : longint ) : longint;
begin
  if a > b then fmax := a else fmax := b;
end;

function fmin ( a , b : longint ) : longint;
begin
  if a < b then fmin := a else fmin := b;
end;

procedure init;
var
        i               : longint;
        t1 , t2 , t3    : longint;

begin
  readln;
  readln ( n );
  for i := 1 to n do
  begin
    last [ i ] := 0;
    fa [ i ] := 0;
    go [ i ] := 0;
    depth [ i ] := 0;
    treebelong [ i ] := 0;
  end;

  e := 0;
  for i := 1 to n - 1 do
  begin
    readln ( t1 , t2 , t3 );
    add_edge ( t1 , t2 , t3 );
  end;
end;

procedure dfs ( step , root , lastedge : longint );
var
        w , tmp , node  : longint;

begin
  depth [ root ] := step;
  inc ( stsize );
  st [ stsize ] := root;
  sa_st [ root ] := stsize;
  sum [ root ] := 0;
  sa_point [ root ] := ( lastedge + 1 ) shr 1;
  sa_edge [ ( lastedge + 1 ) shr 1 ] := root;
  len [ ( lastedge + 1 ) shr 1 ] := edge [ lastedge ] . len;
  tmp := 0;   node := 0;
  w := last [ root ];
  while w <> 0 do
  begin
    if depth [ edge [ w ] . go ] = 0 then
    begin
      dfs ( step + 1 , edge [ w ] . go , w );
      inc ( stsize );
      st [ stsize ] := root;
      fa2 [ edge [ w ] . go ] := root;
      if sum [ edge [ w ] . go ] > tmp then
      begin
        tmp := sum [ edge [ w ] . go ];
        node := edge [ w ] . go;
      end;
      inc ( sum [ root ] , sum [ edge [ w ] . go ] );
    end;
    w := edge [ w ] . pre;
  end;
  if node <> 0 then
  begin
    fa [ node ] := root;
    go [ root ] := node;
  end;
  inc ( sum [ root ] );
end;

procedure pass ( x : longint );
var
        i               : longint;
        ch              : char;

begin
  for i := 1 to x do read ( ch );
end;

procedure build_RMQ;
var
        i , j , len     : longint;

begin
  j := 0;
  for i := 1 to stsize do
  begin
    while 1 shl ( j + 1 ) <= i do inc ( j );
    lg [ i ] := j;
  end;
  for i := 1 to stsize do f [ 0 , i ] := st [ i ];
  for i := 1 to maxlg do
  begin
    len := 1 shl i;
    for j := 1 to stsize - len + 1 do
    begin
      if depth [ f [ i - 1 , j ] ] < depth [ f [ i - 1 , j + len shr 1 ] ] then f [ i , j ] := f [ i - 1 , j ]
      else f [ i , j ] := f [ i - 1 , j + len shr 1 ];
    end;
  end;
end;

procedure swap ( var a , b : longint );
var
        tmp             : longint;

begin
  tmp := a;
  a := b;
  b := tmp;
end;

function get_RMQ ( a , b : longint ) : longint;
var
        j               : longint;

begin
  if a = b then exit ( a );
  if a > b then swap ( a , b );
  j := lg [ ( b - a + 1 ) ];
  get_RMQ := fmin ( f [ j , a ] , f [ j , b - 1 shl j + 1 ] );
end;

procedure get_tree ( root : longint );
begin
  if root = 0 then exit;
  if fa [ root ] <> 0 then
  begin
    inc ( tree2 );
    get [ tree2 ] := sa_point [ root ];
    treeposi [ sa_point [ root ] ] := tree2;
    treebelong [ get [ tree2 ] ] := tree1;
  end;
  get_tree ( go [ root ] );
  visited [ root ] := true;
end;

procedure build_tree ( x , left , right : longint );
var
        mid             : longint;

begin
  inc ( po );
  if left = right then
  begin
    inc ( e );
    tree [ x ] . max := len [ get [ e ] ];
    tree [ x ] . min := len [ get [ e ] ];
    tree [ x ] . left := 0;
    tree [ x ] . right := 0;
    tree [ x ] . sign := false;
    exit;
  end;
  mid := ( left + right ) shr 1;
  tree [ x ] . left := po + 1;
  build_tree ( po + 1 , left , mid );
  tree [ x ] . right := po + 1;
  build_tree ( po + 1 , mid + 1 , right );
  tree [ x ] . max := fmax ( tree [ tree [ x ] . left ] . max , tree [ tree [ x ] . right ] . max );
  tree [ x ] . min := fmin ( tree [ tree [ x ] . left ] . min , tree [ tree [ x ] . right ] . min );
  tree [ x ] . sign := false;
end;

procedure build_segment_tree;
var
        i               : longint;

begin
  fillchar ( visited , sizeof ( visited ) , false );
  tree1 := 0;
  po := 0;
  for i := 1 to stsize do
    if ( not visited [ st [ i ] ] ) and ( go [ st [ i ] ] <> 0 ) then
    begin
      inc ( tree1 );
      tree2 := 0;
      get_tree ( st [ i ] );
      e := 0;
      treeroot [ tree1 ] := po + 1;
      treefirst [ tree1 ] := st [ i ];
      size [ tree1 ] := tree2;
      build_tree ( po + 1 , 1 , tree2 );
    end;
end;

procedure maintain ( x , left ,right : longint );
var
        lc , rc , tmp   : longint;

begin
  if tree [ x ] . sign then
  begin
    tree [ x ] . sign := false;
    if left <> right then
    begin
      tree [ tree [ x ] . left ] . sign := not tree [ tree [ x ] . left ] . sign;
      tree [ tree [ x ] . right ] . sign := not tree [ tree [ x ] . right ] . sign;
    end;
    tmp := tree [ x ] . max;
    tree [ x ] . max := -tree [ x ] . min;
    tree [ x ] . min := -tmp;
  end;
end;

function tree_find ( x , left , right , t1 , t2 : longint ) : longint;
var
        mid , tmp       : longint;

begin
  maintain ( x , left , right );
  if ( t1 <= left ) and ( right <= t2 ) then exit ( tree [ x ] . max );
  mid := ( left + right ) shr 1;
  tmp := -maxvalue;
  if ( t1 <= mid ) and ( left <= t2 ) then tmp := fmax ( tmp , tree_find ( tree [ x ] . left , left , mid , t1 , t2 ) );
  if ( t1 <= right ) and ( mid + 1 <= t2 ) then tmp := fmax ( tmp , tree_find ( tree [ x ] . right , mid + 1 , right , t1 , t2 ) );
  tree_find := tmp;
end;

function _query_get ( a , b : longint ) : longint;
var
        tmp             : longint;

begin
  tmp := -maxvalue;
  repeat
    if depth [ a ] <= depth [ b ] then break;
    if fa [ a ] = 0 then
    begin
      tmp := fmax ( tmp , len [ sa_point [ a ] ] );
      a := fa2 [ a ];
    end
    else
    begin
      if treebelong [ sa_point [ a ] ] <> treebelong [ sa_point [ b ] ] then tmp := fmax ( tmp , tree_find ( treeroot [ treebelong [ sa_point [ a ] ] ] , 1 , size [ treebelong [ sa_point [ a ] ] ] , 1 , treeposi [ sa_point [ a ] ] ) )
      else tmp := fmax ( tmp , tree_find ( treeroot [ treebelong [ sa_point [ a ] ] ] , 1 , size [ treebelong [ sa_point [ a ] ] ] , treeposi [ sa_point [ b ] ] + 1 , treeposi [ sa_point [ a ] ] ) );
      a := treefirst [ treebelong [ sa_point [ a ] ] ];
    end;
  until false;
  _query_get := tmp;
end;

function _query ( a , b : longint ) : longint;
var
        ance , u , v    : longint;

begin
  ance := get_RMQ ( sa_st [ a ] , sa_st [ b ] );
  u := _query_get ( a , ance );
  v := _query_get ( b , ance );
  writeln ( fmax ( u , v ) );
end;

procedure tree_modify ( x , left , right , k , t : longint );
var
        mid             : longint;

begin
  maintain ( x , left , right );
  if left = right then
  begin
    tree [ x ] . max := t;
    tree [ x ] . min := t;
    exit;
  end;
  mid := ( left + right ) shr 1;
  if k <= mid then tree_modify ( tree [ x ] . left , left , mid , k , t )
  else tree_modify ( tree [ x ] . right , mid + 1 , right , k , t );
  tree [ x ] . max := fmax ( tree [ tree [ x ] . left ] . max , tree [ tree [ x ] . right ] . max );
  tree [ x ] . min := fmin ( tree [ tree [ x ] . left ] . min , tree [ tree [ x ] . right ] . min );
end;

procedure _change ( a , b : longint );
begin
  if fa [ sa_edge [ a ] ] = 0 then len [ a ] := b
  else tree_modify ( treeroot [ treebelong [ a ] ] , 1 , size [ treebelong [ a ] ] , treeposi [ a ] , b );
end;

procedure tree_insert ( x , left , right , t1 , t2 : longint );
var
        mid             : longint;

begin
  maintain ( x , left , right );
  if ( t1 <= left ) and ( right <= t2 ) then
  begin
    tree [ x ] . sign := true;
    maintain ( x , left , right );
    exit;
  end;
  mid := ( left + right ) shr 1;
  if ( t1 <= mid ) and ( left <= t2 ) then tree_insert ( tree [ x ] . left , left , mid , t1 , t2 );
  if ( t1 <= right ) and ( mid + 1 <= t2 ) then tree_insert ( tree [ x ] . right , mid + 1 , right , t1 , t2 );
  tree [ x ] . max := fmax ( tree [ tree [ x ] . left ] . max , tree [ tree [ x ] . right ] . max );
  tree [ x ] . min := fmin ( tree [ tree [ x ] . left ] . min , tree [ tree [ x ] . right ] . min );
end;

procedure _negate_get ( a , b : longint );
begin
  repeat
    if depth [ a ] <= depth [ b ] then break;
    if fa [ a ] = 0 then
    begin
      len [ sa_point [ a ] ] := - len [ sa_point [ a ] ];
      a := fa2 [ a ];
    end
    else
    begin
      if treebelong [ sa_point [ a ] ] <> treebelong [ sa_point [ b ] ] then tree_insert ( treeroot [ treebelong [ sa_point [ a ] ] ] , 1 , size [ treebelong [ sa_point [ a ] ] ] , 1 , treeposi [ sa_point [ a ] ] )
      else tree_insert ( treeroot [ treebelong [ sa_point [ a ] ] ] , 1 , size [ treebelong [ sa_point [ a ] ] ] , treeposi [ sa_point [ b ] ] + 1 , treeposi [ sa_point [ a ] ] );
      a := treefirst [ treebelong [ sa_point [ a ] ] ];
    end;
  until false;
end;

procedure _negate ( a , b : longint );
var
        ance , u , v    : longint;

begin
  ance := get_RMQ ( sa_st [ a ] , sa_st [ b ] );
  _negate_get ( a , ance );
  _negate_get ( b , ance );
end;

procedure main;
var
        ch              : char;
        t1 , t2         : longint;

begin
  stsize := 0;
  dfs ( 1 , 1 , 0 );
  sa_edge [ 0 ] := 0;
  build_segment_tree;
  build_RMQ;
  repeat
    read ( ch );
    case ch of
      'Q' : begin
              pass ( 4 );
              readln ( t1 , t2 );
              _query ( t1 , t2 );
            end;

      'C' : begin
              pass ( 5 );
              readln ( t1 , t2 );
              _change ( t1 , t2 );
            end;

      'N' : begin
              pass ( 5 );
              readln ( t1 , t2 );
              _negate ( t1 , t2 );
            end;

      'D' : begin
              pass ( 3 );
              readln;
              exit;
            end;
    end;
  until false;
end;

begin
  assign ( input , 'pku3237.in' );
  assign ( output , 'pku3237.out' );
  reset ( input );
  rewrite ( output );
  readln ( test );
  for test := 1 to test do
  begin
    init;
    main;
  end;
  close ( input );
  close ( output );
end.

• Re:为什么我的程序一直WA,谁能给我一组WA的数据 (13157) gongshaoqing 2009-11-24 11:16:53