TrickmanOff

Untitled

Dec 19th, 2019
282
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.40 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <fstream>
  4. #include <vector>
  5. #include <queue>
  6. #include <functional>
  7. #include <set>
  8. #include <map>
  9. #include <math.h>
  10. #include <cmath>
  11. #include <string>
  12. #include <time.h>
  13. #include <random>
  14. #include <unordered_set>
  15. #include <unordered_map>
  16. #include <bitset>
  17. #include <string.h>
  18. #include <stack>
  19. using namespace std;
  20. //
  21. #define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
  22. #define cin in
  23. #define cout out
  24. #define pii pair<int,int>
  25. #define ll long long
  26. #define db double
  27. #define ld long double
  28. #define uset unordered_set
  29. #define umap unordered_map
  30. #define F first
  31. #define S second
  32. #define vec vector
  33. #define ms multiset
  34. #define pb push_back
  35. #define pll pair<ll,ll>
  36. #define pdd pair<ld, ld>
  37. #define pq priority_queue
  38. #define umap unordered_map
  39. #define uset unordered_set
  40. #define pii pair<int, int>
  41. #define pll pair<ll, ll>
  42. #define pnn pair<Node*, Node*>
  43. #define uid uniform_int_distribution
  44.  
  45. ifstream in("input.txt");
  46. ofstream out("output.txt");
  47.  
  48. const int MAX_N = 1e5;
  49. int n, cl[MAX_N], t_sz[MAX_N];
  50. vector<int> g[MAX_N];
  51. bool used[MAX_N];
  52.  
  53. void input() {
  54. cin >> n;
  55.  
  56. for (int i = 0; i < n - 1; i++) {
  57. int a;
  58. cin >> a;
  59. a--;
  60. g[i].push_back(a);
  61. g[a].push_back(i);
  62. }
  63.  
  64. for (int i = 0; i < n; i++)
  65. cin >> cl[i];
  66. }
  67.  
  68. vector<int> cent[MAX_N];
  69.  
  70. int get_size(int v, int p) {
  71. t_sz[v] = 1;
  72. for (int to : g[v]) {
  73. if (!used[to] && to != p)
  74. t_sz[v] += get_size(to, v);
  75. }
  76. return t_sz[v];
  77. }
  78.  
  79. int get_cent(int v, int p, int sz) {
  80. for (int to : g[v]) {
  81. if (!used[to] && to != p && 2 * t_sz[to] >= sz)
  82. return get_cent(to, v, sz);
  83. }
  84.  
  85. used[v] = 1;
  86. return v;
  87. }
  88.  
  89. void process(int v, int p, int cent) {
  90.  
  91. }
  92.  
  93. void build(int v) {
  94. v = get_cent(v, -1, get_size(v, -1));
  95.  
  96.  
  97. }
  98.  
  99. int main() {
  100. input();
  101. memset(used, 0, sizeof(used));
  102. }
  103.  
  104. /*
  105. Для каждого центроида найдём расстояние до каждой вершины в его компоненте
  106. N logN
  107. map<int, int> dist;
  108.  
  109.  
  110. Мин расстояние от центроида до вершины каждого из цветов в каждом центроиде
  111. N logN
  112. map<int, int> dist_cl;
  113.  
  114.  
  115. Для каждой вершины храним список центроидов, в компоненты которых она входит
  116. N logN
  117. vector<int> cent[MAX_N];
  118.  
  119.  
  120. */
Advertisement
Add Comment
Please, Sign In to add comment