Guest User

Untitled

a guest
Dec 5th, 2019
32
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct node{
  5. int id;
  6. int depth;
  7. int subtree_sz;
  8. int color; //0 is white, 1 is black
  9. vector<node*> nodesonpath;
  10. vector<node*> neighbors;
  11. set<int> blacknodes;
  12. node* parent;
  13. node* headnode; // head of heavy-path
  14. };
  15.  
  16. node* newNode(int id){
  17. node* n = new node;
  18. n->id = id;
  19. n->parent = n->headnode = NULL;
  20. n->color = 0;
  21. return n;
  22. }
  23.  
  24. int x,y,z;
  25.  
  26. void dfs(node* n, node* parent){
  27. if(!parent){
  28. n->depth = 0; //root
  29. }
  30. else n->depth = parent->depth + 1;
  31.  
  32. //sets up subtree sizes, lca stuff
  33. n->parent = parent;
  34. n->subtree_sz = 1;
  35. for(int i = 0; i < n->neighbors.size(); i++){
  36. if(n->neighbors[i] == parent) continue;
  37. dfs(n->neighbors[i],n);
  38. n->subtree_sz += n->neighbors[i]->subtree_sz;
  39. }
  40. }
  41.  
  42. void dfs_hld(node* n, node* parent, node* headnode){
  43. n->headnode = headnode;
  44. headnode->nodesonpath.push_back(n);
  45. for(auto &n1 : n->neighbors){
  46. if(n1 == parent) continue;
  47. if(n1->subtree_sz > (n->subtree_sz - 1)/2)
  48. dfs_hld(n1,n,headnode);
  49. else
  50. dfs_hld(n1,n,n1);
  51. }
  52. }
  53.  
  54. vector<node*> nodes;
  55.  
  56. void change(node* &n){
  57. if(n->color == 0){
  58. //white
  59. n->color = 1;
  60. n->headnode->blacknodes.insert(n->id);
  61. }
  62. else{
  63. //black
  64. n->color = 0;
  65. n->headnode->blacknodes.erase(n->id);
  66. }
  67. }
  68.  
  69. int findmin(node* &n){
  70. int minval = -2, temp;
  71. node* ncur = n;
  72. while(ncur){
  73. if(!ncur->headnode->blacknodes.empty()){
  74. temp = *(ncur->headnode->blacknodes.begin());
  75. if(nodes[temp]->depth <= ncur->depth) minval = temp;
  76. }
  77. ncur = ncur->headnode->parent;
  78. }
  79. return 1+minval;
  80. }
  81.  
  82. void addEdge(int a, int b){
  83. nodes[a]->neighbors.push_back(nodes[b]);
  84. nodes[b]->neighbors.push_back(nodes[a]);
  85. }
  86.  
  87. int main(){
  88. ios_base::sync_with_stdio(false);
  89. cin.tie(NULL);
  90.  
  91. int N,Q;
  92. cin >> N >> Q;
  93. nodes.resize(N);
  94. for(int i = 0; i < N; i++)
  95. nodes[i] = newNode(i);
  96.  
  97. for(int i = 0; i < N-1; i++){
  98. cin >> x >> y;
  99. addEdge(x-1,y-1);
  100. }
  101. dfs(nodes[0],NULL);
  102. dfs_hld(nodes[0],NULL,nodes[0]);
  103. int query;
  104. while(Q--){
  105. cin >> query >> x;
  106. if(query == 0){
  107. change(nodes[x-1]);
  108. }
  109. else{
  110. cout << findmin(nodes[x-1]) << endl;
  111. }
  112. }
  113.  
  114. return 0;
  115. }
RAW Paste Data