http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3145

给一个森林，每条边有一种颜色，有3种操作，A、将以x于其父亲断开并连到y上；B、将x到y路上的边染成颜色c；C、询问x到y的路的长度以及路上有多少种颜色。

比较赤裸的动态树问题，强烈推荐杨哲的《QTREE解法的一些研究》，其上对于link_cut tree 的介绍通俗易懂。

这里我稍微讲一下题目中要注意的地方，其中这里每条边都有自己独立的属性，颜色。而标准的link_cut tree.中的节点表示的树上的点，对于边的属性放在哪个点上这里要非常非常仔细的考虑！一开始我想当然的以为两个端点中低的那个点=。=～结果可想而知。。这里我下一个详尽的定义：对于splay上的节点，其记录的边是以其为根的splay子树，与这条链（一整棵splay树是实际中的一条链）其他部分链接的边。。这里再次强烈建议Rotate的时候，画图把边标上号，弄清楚边的转移。

其次，对于Link_cut tree中的虚边，可以借用splay tree的*fa存在即可。

恩，从此我也有动态树模板拉～

1 //By Lin  2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #define X first  7 #define Y second  8 #define mp(x,y) make_pair(x,y)  9 #define Rep(i,n) for(int i = 0; i
          
            pii; 12  13 #define    N 100015 14 int        n,m; 15 struct    Splaynode{ 16     Splaynode *fa,*ch[2]; 17     int        key,c,mark,size,id; 18     bool    rev; 19     void    updata(){ 20         key = 0; 21         size = 1; 22         Rep(i,2) if ( ch[i] ) 23             key |= ch[i]->key | (1<
           
            c) , 24 size += ch[i]->size; 25 } 26 void down(){ 27 if ( mark ){ 28 if ( ch[0] ) { 29 ch[0]->c = ch[0]->mark = mark; 30 ch[0]->key = key; 31 } 32 if ( ch[1] ) { 33 ch[1]->c = ch[1]->mark = mark; 34 ch[1]->key = key; 35 } 36 mark = 0; 37 } 38 if ( rev ){ 39 if ( ch[0] ) ch[0]->rev ^= 1; 40 if ( ch[1] ) ch[1]->rev ^= 1; 41 swap( ch[0] , ch[1] ); 42 } 43 rev = false; 44 } 45 }node[N]; 46 47 struct LCT{ 48 void Rotate( Splaynode *x ) { 49 Splaynode *y = x->fa; 50 int col = y->c; 51 int d = y->ch[1] == x; 52 if ( x->fa = y->fa ) { 53 if ( y->fa->ch[0] == y ) y->fa->ch[0] = x; 54 if ( y->fa->ch[1] == y ) y->fa->ch[1] = x; 55 } 56 if ( y->ch[d] = x->ch[d^1] ) { 57 y->ch[d]->fa = y; 58 y->c = y->ch[d]->c; 59 y->ch[d]->c = x->c; 60 x->c = col; 61 } 62 else swap(x->c,y->c); 63 x->ch[d^1] = y; 64 y->fa = x; 65 y->updata(); 66 x->updata(); 67 } 68 inline bool is_root( Splaynode *u ){ 69 if ( !u->fa ) return true; 70 return (u->fa->ch[0]!=u && u->fa->ch[1]!=u ); 71 } 72 void Splay( Splaynode *x ){ 73 stack
            
              g; 74 Splaynode *tmp = x; 75 while ( true ){ 76 g.push( tmp ); 77 if ( is_root(tmp) ) break; 78 tmp = tmp->fa; 79 } 80 while ( !g.empty() ){ 81 g.top()->down(); 82 g.pop(); 83 } 84 while ( !is_root(x) ){ 85 if ( is_root(x->fa) ) Rotate(x); 86 else { 87 int d1 = x->fa->fa->ch[1] == x->fa, 88 d2 = x->fa->ch[1] == x; 89 if ( d1 == d2 ) Rotate(x->fa),Rotate(x); 90 else Rotate(x),Rotate(x); 91 } 92 } 93 } 94 void Access( Splaynode* u ){ 95 Splaynode *v = NULL; 96 for (; u; u = u->fa ){ 97 Splay(u); 98 u->ch[1] = v; 99 (v=u)->updata();100 }101 }102 void Cut( Splaynode* u ) {103 Access(u);104 Splay(u);105 if ( u->ch[0] ) {106 u->ch[0]->fa = NULL;107 u->ch[0]->c = 0;108 }109 u->ch[0] = NULL;110 }111 void Link( Splaynode *u, Splaynode *v ,int col ) {112 Access(v);113 Splay(u);114 Splaynode *tmp = u;115 while ( !is_root(tmp) ) tmp = tmp->fa;116 if ( tmp == v ) return;117 Cut(u);118 u->fa = v;119 u->c = col;120 }121 Splaynode* GetRoot( Splaynode* u){122 Access(u);123 Splay(u);124 Splaynode* ret = u;125 while ( ret->ch[0] ) ret = ret->ch[0];126 Splay(ret);127 return ret;128 }129 void MakeRoot( Splaynode* u){130 Access(u);131 Splay(u);132 u->rev ^= 1; 133 }134 void Set( Splaynode *u , Splaynode *v ,int col ) {135 Splaynode *root = GetRoot(u);136 if ( root != GetRoot(v) ) return;137 MakeRoot(u);138 Access(v);139 Splay(v);140 v->mark = col;141 v->key = 1<
             
              key; 151 pii ret(v->size-1,0);152 while ( k ) { ret.Y += k&1; k >>= 1; }153 MakeRoot(root);154 return ret;155 }156 }tree;157 158 int main(){159 int kind,u,v,col;160 pii ans;161 while ( ~scanf("%d%d", &n, &m ) ) {162 memset( node , 0 , sizeof(node) );163 for (int i = 1; i<=n; i++) {164 scanf("%d", &u );165 if ( u ) node[i].fa = &node[u];166 node[i].id = i;167 }168 for (int i = 1; i<=n; i++) {169 scanf("%d", &u );170 if ( node[i].fa ) node[i].c = u;171 }172 while ( m -- ) {173 scanf("%d", &kind );174 switch ( kind ) {175 case 1:176 scanf("%d%d%d", &u, &v, &col );177 tree.Link( &node[u] , &node[v], col );178 break;179 case 2:180 scanf("%d%d%d", &u, &v, &col );181 tree.Set( &node[u] , &node[v], col );182 break;183 default:184 scanf("%d%d", &u, &v );185 ans = tree.Ask( &node[u], &node[v] );186 printf("%d %d\n" , ans.X , ans.Y );187 }188 }189 }190 return 0;191 }