fork download
copy 
  1. /***********Template Starts Here***********/
  2. #include <bits/stdc++.h>
  3.  
  4. #define pb push_back
  5. #define nl puts ("")
  6. #define sp printf ( " " )
  7. #define phl printf ( "hello\n" )
  8. #define ff first
  9. #define ss second
  10. #define POPCOUNT __builtin_popcountll
  11. #define RIGHTMOST __builtin_ctzll
  12. #define LEFTMOST(x) (63-__builtin_clzll((x)))
  13. #define MP make_pair
  14. #define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)
  15. #define ROF(i,x,y) for(vlong i = (y) ; i >= (x) ; --i)
  16. #define CLR(x,y) memset(x,y,sizeof(x))
  17. #define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
  18. #define MIN(a,b) ((a)<(b)?(a):(b))
  19. #define MAX(a,b) ((a)>(b)?(a):(b))
  20. #define NUMDIGIT(x,y) (((vlong)(log10((x))/log10((y))))+1)
  21. #define SQ(x) ((x)*(x))
  22. #define ABS(x) ((x)<0?-(x):(x))
  23. #define FABS(x) ((x)+eps<0?-(x):(x))
  24. #define ALL(x) (x).begin(),(x).end()
  25. #define LCM(x,y) (((x)/gcd((x),(y)))*(y))
  26. #define SZ(x) ((vlong)(x).size())
  27. #define NORM(x) if(x>=mod)x-=mod;
  28.  
  29. using namespace std;
  30.  
  31. typedef long long vlong;
  32. typedef unsigned long long uvlong;
  33. typedef pair < int, int > pii;
  34. typedef pair < vlong, vlong > pll;
  35. typedef vector<pii> vii;
  36. typedef vector<int> vi;
  37.  
  38. const vlong inf = 2147383647;
  39.  
  40. /***********Template Ends Here***********/
  41.  
  42. #define LCANODE 100010
  43. #define LCADEPTH 20
  44. vi adj[LCANODE];
  45. struct LCA{
  46.     private:
  47.     int tab[LCANODE][LCADEPTH], lev[LCANODE], vis[LCANODE], q[LCANODE], cc, N, M, root;
  48.  
  49.     public:
  50.     int par[LCANODE];
  51.  
  52.     private:
  53.     void bfs ( int s ) {
  54.         vis[s] = cc;
  55.         lev[s] = 0;
  56.         par[s] = -1; ///Set par[root] = -1
  57.  
  58.         int qh = 0, qt = 0;
  59.         q[qt++] = s;
  60.         int t;
  61.         while ( qh < qt ) {
  62.             s = q[qh++];
  63.             FOR(i,0,SZ(adj[s])-1){
  64.                 t = adj[s][i];
  65.                 if ( vis[t] != cc ) {
  66.                     par[t] = s;
  67.                     vis[t] = cc;
  68.                     lev[t] = lev[s] + 1;
  69.                     q[qt++] = t;
  70.                 }
  71.             }
  72.         }
  73.     }
  74.  
  75.     void calculate (){
  76.         int i,j,p;
  77.         for (i=0;i<=N;i++){
  78.            tab[i][0]=par[i];
  79.         }
  80.  
  81.         for(i=1;i<=M;i++){
  82.             for(j=0;j<=N;j++){
  83.                 p=tab[j][i-1];
  84.                 if(p==-1) tab[j][i]=-1;
  85.                 else tab[j][i]=tab[p][i-1];
  86.             }
  87.         }
  88.     }
  89.  
  90.     public:
  91.     void clear () {
  92.         cc++;
  93.         FOR(i,0,N) adj[i].clear();
  94.     }
  95.  
  96.     LCA() {
  97.         cc = 1;
  98.     }
  99.  
  100.     void setVar ( int n, int r ) {
  101.         N = n;
  102.  
  103.         M = 0;
  104.         int temp = n+1;
  105.         while ( temp ) {
  106.             M++;
  107.             temp /= 2;
  108.         }
  109.         root = r;
  110.         clear();
  111.     }
  112.     void precal () {
  113.         bfs ( root );
  114.         calculate();
  115.     }
  116.     int findLCA(int s,int t){
  117.         int dif,pos,i;
  118.         if(lev[s]!=lev[t] ) {
  119.             if(lev[s]>lev[t]) swap( s, t );
  120.             dif=lev[t]-lev[s];
  121.             while(dif){
  122.                 pos=RIGHTMOST(dif);
  123.                 t=tab[t][pos];
  124.                 dif-=1<<pos;
  125.             }
  126.         }
  127.         if (s==t)return s;
  128.         for(i=M;i>=0;i--){
  129.             if(tab[s][i]!=tab[t][i]){
  130.                 s=tab[s][i];
  131.                 t=tab[t][i];
  132.             }
  133.         }
  134.         return tab[s][0];
  135.     }
  136. }lca;
  137.  
  138. int child[100010];
  139. int pretrav[100010], pre = 0;
  140. int preStart[100010];
  141. void dfs ( int s, int p ) {
  142.     child[s] = 1;
  143.     preStart[s] = pre;
  144.     pretrav[pre++] = s;
  145.  
  146.     FOR(i,0,SZ(adj[s])-1){
  147.         int t = adj[s][i];
  148.         if ( t == p ) continue;
  149.         dfs ( t, s );
  150.         child[s] += child[t];
  151.     }
  152. }
  153.  
  154. int color[100010], arr[11][100010];
  155.  
  156. void dfs2 ( int s, int p, int d, int c ) {
  157.     arr[c][s] = d;
  158.  
  159.     FOR(i,0,SZ(adj[s])-1){
  160.         int t = adj[s][i];
  161.         if ( t == p ) continue;
  162.         int cost = 0;
  163.         if ( color[t] == c ) cost = 1;
  164.  
  165.         dfs2 ( t, s, d + cost, c );
  166.     }
  167. }
  168.  
  169. struct node {
  170.     int val;
  171.     int lazy;
  172. }tn[11][4*100000];
  173.  
  174. void build ( int col, int t, int b, int e ) {
  175.     int m = ( b + e ) / 2;
  176.     int u = t * 2;
  177.     int v = u + 1;
  178.  
  179.     tn[col][t].lazy = 0; ///lazyClear();
  180.  
  181.     if ( b == e ) {
  182.         tn[col][t].val = arr[col][pretrav[b]];
  183.         return;
  184.     }
  185.  
  186.     build( col, u, b, m );
  187.     build( col, v, m + 1, e );
  188. }
  189.  
  190. int qb, qe, qv;
  191. void lazyPropagate ( node &p, node &u, node &v ) {
  192.     u.lazy += p.lazy;
  193.     v.lazy += p.lazy;
  194. }
  195.  
  196. void update ( int col, int t, int b, int e ) {
  197.     int m = ( b + e ) / 2;
  198.     int u = t * 2;
  199.     int v = u + 1;
  200.  
  201.     if ( qb <= b && e <= qe ) {
  202.         tn[col][t].lazy += qv;///lazyUpdate();
  203.         tn[col][t].val += tn[col][t].lazy;///calculate();
  204.         if ( b != e ) lazyPropagate ( tn[col][t], tn[col][u], tn[col][v] );
  205.         tn[col][t].lazy = 0; ///LazyClear
  206.         return;
  207.     }
  208.     if ( qe < b || e < qb ) {
  209.         tn[col][t].val += tn[col][t].lazy;///calculate();
  210.         if ( b != e ) lazyPropagate ( tn[col][t], tn[col][u], tn[col][v] );
  211.         tn[col][t].lazy = 0; ///LazyClear
  212.         return;
  213.     }
  214.  
  215.     lazyPropagate ( tn[col][t], tn[col][u], tn[col][v] );
  216.     tn[col][t].lazy = 0; ///LazyClear
  217.  
  218.     update( col, u, b, m );
  219.     update( col, v, m + 1, e );
  220.  
  221. }
  222.  
  223. int qvv[11];
  224.  
  225. void query ( int t, int b, int e ) {
  226.     int m = ( b + e ) / 2;
  227.     int u = t * 2;
  228.     int v = u + 1;
  229.  
  230.     if ( qb <= b && e <= qe ) {
  231.         FOR(i,1,10) tn[i][t].val += tn[i][t].lazy;///calculate();
  232.         if ( b != e ) {
  233.             FOR(i,1,10) lazyPropagate ( tn[i][t], tn[i][u], tn[i][v] );
  234.         }
  235.         FOR(i,1,10) tn[i][t].lazy = 0; ///LazyClear
  236.         FOR(i,1,10) qvv[i] = tn[i][t].val;
  237.         return;
  238.     }
  239.     if ( qe < b || e < qb ) {
  240.         FOR(i,1,10) tn[i][t].val += tn[i][t].lazy;///calculate();
  241.         if ( b != e ) {
  242.             FOR(i,1,10) lazyPropagate ( tn[i][t], tn[i][u], tn[i][v] );
  243.         }
  244.         FOR(i,1,10) tn[i][t].lazy = 0; ///LazyClear
  245.         return;
  246.     }
  247.  
  248.     FOR(i,1,10) lazyPropagate ( tn[i][t], tn[i][u], tn[i][v] );
  249.     FOR(i,1,10) tn[i][t].lazy = 0; ///LazyClear
  250.  
  251.     query( u, b, m );
  252.     query( v, m + 1, e );
  253.  
  254. }
  255.  
  256. int main () {
  257.  
  258.     int kase;
  259.     scanf ( "%d", &kase );
  260.  
  261.     while ( kase-- ) {
  262.         int n, m;
  263.         scanf ( "%d %d", &n, &m );
  264.  
  265.         lca.setVar( n, 0 );
  266.  
  267.         CLR(color,0);
  268.         FOR(i,1,n){
  269.             int c;
  270.             scanf ( "%d", &c );
  271.             color[i] = c; ///Set color
  272.         }
  273.  
  274.         FOR(i,0,n-2){
  275.             int a, b;
  276.             scanf ( "%d %d", &a, &b );
  277.             adj[a].pb ( b );
  278.             adj[b].pb ( a );
  279.         }
  280.         adj[0].pb ( 1 ); ///Dummy node
  281.  
  282.         lca.precal();
  283.  
  284.         pre = 0;
  285.         dfs ( 0, -1 ); ///Calculate child, starting position in pre-traversal
  286.  
  287.         ///Calculate distance in each color tree
  288.         FOR(i,1,10){
  289.             dfs2 ( 0, -1, 0, i );
  290.         }
  291.  
  292.  
  293.         ///Preparations complete. Start segment tree
  294.         FOR(i,1,10) {
  295.             build ( i, 1, 0, n );
  296.         }
  297.  
  298.         while ( m-- ) {
  299.             int t;
  300.             scanf ( "%d", &t );
  301.  
  302.             if ( t == 0 ) {
  303.                 int u, c;
  304.                 scanf ( "%d %d", &u, &c );
  305.  
  306.                 ///Change color from color[u] to c
  307.                 int p = color[u];
  308.                 ///Update the subtree of u of color p with -1
  309.                 qb = preStart[u]; qe = qb + child[u] - 1; qv = -1;
  310.                 update ( p, 1, 0, n );
  311.  
  312.                 ///Update the subtree of u of color c with +1
  313.                 qv = 1;
  314.                 update ( c, 1, 0, n );
  315.                 color[u] = c;
  316.             }
  317.             else {
  318.                 int u, v;
  319.                 scanf ( "%d %d", &u, &v );
  320.  
  321.                 ///Find distance in each color tree
  322.                 int res = 0;
  323.  
  324.                 int tres[11];
  325.                 CLR(tres,0);
  326.  
  327.                 qb = preStart[u]; qe = qb;
  328.                 query( 1, 0, n );
  329.  
  330.                 FOR(i,1,10) tres[i] = qvv[i];
  331.  
  332.  
  333.                 qb = preStart[v]; qe = qb;
  334.                 query( 1, 0, n );
  335.  
  336.                 FOR(i,1,10) tres[i] += qvv[i];
  337.  
  338.                 int par = lca.findLCA( u, v );
  339.  
  340.                 qb = preStart[par]; qe = qb;
  341.                 query( 1, 0, n );
  342.                 FOR(i,1,10) tres[i] -= 2 * qvv[i];
  343.  
  344.                 FOR(i,1,10){
  345.                     int col = color[par];
  346.                     if ( col == i ) tres[i]++;
  347.                 }
  348.  
  349.                 FOR(i,1,10) res = MAX(res,tres[i]);
  350.  
  351.                 printf ( "%d\n", res );
  352.             }
  353.         }
  354.     }
  355.  
  356.     return 0;
  357. }
  358.  
Runtime error #stdin #stdout 0s 54248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/UEU9J4
Blog UVa 12424 - Answering Queries on a Tree
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!