Advertisement
dipBRUR

DSU on tree

Oct 4th, 2018
160
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.22 KB | None | 0 0
  1. static const int maxn = 1e5 + 5;  
  2.  
  3. vector <int> graph[maxn];  
  4. int color[maxn], subtreeSize[maxn], cnt[maxn];  
  5. bool big[maxn];  
  6.  
  7. // Calculate size of the subtree of every vertices  
  8. void dfs(int u, int p = -1)  
  9. {  
  10.     subtreeSize[u] = 1; // Every vertex has itself in its subtree  
  11.     for (int v : graph[u])  
  12.     {  
  13.         if (v == p)  
  14.             continue;  
  15.         dfs(v, u);  
  16.         subtreeSize[u] += subtreeSize[v]; // Add size of child v to its parent(v)  
  17.     }  
  18. }  
  19.  
  20. void add(int u, int p, int x)  
  21. {  
  22.     cnt[ color[u] ] += x;  
  23.     for (int v : graph[u])  
  24.     {  
  25.         if (v != p || big[v])  
  26.             continue;  
  27.         add(v, u, x);  
  28.     }  
  29. }  
  30.  
  31. void dsu(int u, int p, bool keep)  
  32. {  
  33.     int mx(-1), bigChild(-1);  
  34.     for (int v : graph[u])  
  35.     {  
  36.         if (v == p)  
  37.             continue;  
  38.         if (subtreeSize[v] > mx)  
  39.         {  
  40.             mx = subtreeSize[v];  
  41.             bigChild = v;  
  42.         }  
  43.     }  
  44.     for (int v : graph[u])  
  45.     {  
  46.         if (v == p || v == bigChild)  
  47.             continue;  
  48.         dsu(v, u, 0); // Run a dfs from small child and clear them from cnt  
  49.     }  
  50.     if (bigChild != -1)  
  51.     {  
  52.         dsu(bigChild, u, 1);  
  53.         big[bigChild] = 1; // bigChild marked as big and not cleared from cnt  
  54.     }  
  55.     add(u, p, 1);  
  56.     // cnt[c] is the number of vertices in subtree of vertex u that has color c.  
  57.     if (bigChild != -1)  
  58.         big[bigChild] = 0;  
  59.     if (keep == 0)  
  60.         add(u, p, -1); // remove  
  61. }   static const int maxn = 1e5 + 5;  
  62.  
  63. vector <int> graph[maxn];  
  64. int color[maxn], subtreeSize[maxn], cnt[maxn];  
  65. bool big[maxn];  
  66.  
  67. // Calculate size of the subtree of every vertices  
  68. void dfs(int u, int p = -1)  
  69. {  
  70.     subtreeSize[u] = 1; // Every vertex has itself in its subtree  
  71.     for (int v : graph[u])  
  72.     {  
  73.         if (v == p)  
  74.             continue;  
  75.         dfs(v, u);  
  76.         subtreeSize[u] += subtreeSize[v]; // Add size of child v to its parent(v)  
  77.     }  
  78. }  
  79.  
  80. void add(int u, int p, int x)  
  81. {  
  82.     cnt[ color[u] ] += x;  
  83.     for (int v : graph[u])  
  84.     {  
  85.         if (v != p || big[v])  
  86.             continue;  
  87.         add(v, u, x);  
  88.     }  
  89. }  
  90.  
  91. void dsu(int u, int p, bool keep)  
  92. {  
  93.     int mx(-1), bigChild(-1);  
  94.     for (int v : graph[u])  
  95.     {  
  96.         if (v == p)  
  97.             continue;  
  98.         if (subtreeSize[v] > mx)  
  99.         {  
  100.             mx = subtreeSize[v];  
  101.             bigChild = v;  
  102.         }  
  103.     }  
  104.     for (int v : graph[u])  
  105.     {  
  106.         if (v == p || v == bigChild)  
  107.             continue;  
  108.         dsu(v, u, 0); // Run a dfs from small child and clear them from cnt  
  109.     }  
  110.     if (bigChild != -1)  
  111.     {  
  112.         dsu(bigChild, u, 1);  
  113.         big[bigChild] = 1; // bigChild marked as big and not cleared from cnt  
  114.     }  
  115.     add(u, p, 1);  
  116.     // cnt[c] is the number of vertices in subtree of vertex u that has color c.  
  117.     if (bigChild != -1)  
  118.         big[bigChild] = 0;  
  119.     if (keep == 0)  
  120.         add(u, p, -1); // remove  
  121. }   static const int maxn = 1e5 + 5;  
  122.  
  123. vector <int> graph[maxn];  
  124. int color[maxn], subtreeSize[maxn], cnt[maxn];  
  125. bool big[maxn];  
  126.  
  127. // Calculate size of the subtree of every vertices  
  128. void dfs(int u, int p = -1)  
  129. {  
  130.     subtreeSize[u] = 1; // Every vertex has itself in its subtree  
  131.     for (int v : graph[u])  
  132.     {  
  133.         if (v == p)  
  134.             continue;  
  135.         dfs(v, u);  
  136.         subtreeSize[u] += subtreeSize[v]; // Add size of child v to its parent(v)  
  137.     }  
  138. }  
  139.  
  140. void add(int u, int p, int x)  
  141. {  
  142.     cnt[ color[u] ] += x;  
  143.     for (int v : graph[u])  
  144.     {  
  145.         if (v != p || big[v])  
  146.             continue;  
  147.         add(v, u, x);  
  148.     }  
  149. }  
  150.  
  151. void dsu(int u, int p, bool keep)  
  152. {  
  153.     int mx(-1), bigChild(-1);  
  154.     for (int v : graph[u])  
  155.     {  
  156.         if (v == p)  
  157.             continue;  
  158.         if (subtreeSize[v] > mx)  
  159.         {  
  160.             mx = subtreeSize[v];  
  161.             bigChild = v;  
  162.         }  
  163.     }  
  164.     for (int v : graph[u])  
  165.     {  
  166.         if (v == p || v == bigChild)  
  167.             continue;  
  168.         dsu(v, u, 0); // Run a dfs from small child and clear them from cnt  
  169.     }  
  170.     if (bigChild != -1)  
  171.     {  
  172.         dsu(bigChild, u, 1);  
  173.         big[bigChild] = 1; // bigChild marked as big and not cleared from cnt  
  174.     }  
  175.     add(u, p, 1);  
  176.     // cnt[c] is the number of vertices in subtree of vertex u that has color c.  
  177.     if (bigChild != -1)  
  178.         big[bigChild] = 0;  
  179.     if (keep == 0)  
  180.         add(u, p, -1); // remove  
  181. }   static const int maxn = 1e5 + 5;  
  182.  
  183. vector <int> graph[maxn];  
  184. int color[maxn], subtreeSize[maxn], cnt[maxn];  
  185. bool big[maxn];  
  186.  
  187. // Calculate size of the subtree of every vertices  
  188. void dfs(int u, int p = -1)  
  189. {  
  190.     subtreeSize[u] = 1; // Every vertex has itself in its subtree  
  191.     for (int v : graph[u])  
  192.     {  
  193.         if (v == p)  
  194.             continue;  
  195.         dfs(v, u);  
  196.         subtreeSize[u] += subtreeSize[v]; // Add size of child v to its parent(v)  
  197.     }  
  198. }  
  199.  
  200. void add(int u, int p, int x)  
  201. {  
  202.     cnt[ color[u] ] += x;  
  203.     for (int v : graph[u])  
  204.     {  
  205.         if (v != p || big[v])  
  206.             continue;  
  207.         add(v, u, x);  
  208.     }  
  209. }  
  210.  
  211. void dsu(int u, int p, bool keep)  
  212. {  
  213.     int mx(-1), bigChild(-1);  
  214.     for (int v : graph[u])  
  215.     {  
  216.         if (v == p)  
  217.             continue;  
  218.         if (subtreeSize[v] > mx)  
  219.         {  
  220.             mx = subtreeSize[v];  
  221.             bigChild = v;  
  222.         }  
  223.     }  
  224.     for (int v : graph[u])  
  225.     {  
  226.         if (v == p || v == bigChild)  
  227.             continue;  
  228.         dsu(v, u, 0); // Run a dfs from small child and clear them from cnt  
  229.     }  
  230.     if (bigChild != -1)  
  231.     {  
  232.         dsu(bigChild, u, 1);  
  233.         big[bigChild] = 1; // bigChild marked as big and not cleared from cnt  
  234.     }  
  235.     add(u, p, 1);  
  236.     // cnt[c] is the number of vertices in subtree of vertex u that has color c.  
  237.     if (bigChild != -1)  
  238.         big[bigChild] = 0;  
  239.     if (keep == 0)  
  240.         add(u, p, -1); // remove  
  241. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement