Guest User

Untitled

a guest
Aug 4th, 2021
72
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. #include<bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. #define FOR(i,a,b) for(int i = (a); i < (b); i++)
  7. #define RFOR(i,a,b) for(int i = (a) - 1; i>=(b);i--)
  8. #define rep(i,n) FOR(i,0,n)
  9. #define PB push_back
  10. #define SZ(a) (int)a.size()
  11. #define ALL(a) a.begin(), a.end()
  12. #define FILL(a, value) memset(a, value, sizeof(a))
  13. #define IOS ios_base::sync_with_stdio(0),cin.tie(0), cout.tie(0);
  14. #define f first
  15. #define s second
  16.  
  17.  
  18. typedef long long LL ;
  19. typedef vector<int > VI ;
  20. typedef vector<LL > VL;
  21. typedef pair<int,int > PII;
  22. typedef pair<LL,LL> PLL;
  23.  
  24. const LL LINF = (LL)1e18 +47;
  25. const int INF = (int)1e9 + 47 ;
  26. const int MOD = (int)1e9 + 7;
  27. const int modulo =998244353;
  28. const int nax = (int)1e5 + 100;
  29. const double EPS = 1e-10;
  30. const int K=26;
  31. const double PI = acos(-1.0);
  32. clock_t time_start = clock();
  33.  
  34.  
  35. int clr[nax];
  36. vector<int > g[nax];
  37. set<int> s[nax];
  38. int ans = 0;
  39.  
  40. void merge(int v ,int p )
  41. {
  42.  
  43. VI vec;
  44. FOR(i,0,SZ(g[v]))
  45. {
  46. if(g[v][i] == p)continue;
  47. vec.PB(i);
  48. }
  49. vector<vector<int >>vv(4,VI(SZ(g[v]),0));
  50. vector<vector<int>>can(SZ(g[v]),VI(SZ(g[v]),-1));
  51. FOR(i,0,SZ(vec))
  52. {
  53. FOR(j,0,SZ(vec))
  54. {
  55. if(i == j)continue;
  56. for(auto it :s[g[v][vec[i]]])
  57. {
  58. if(s[g[v][vec[j]]].count(it))
  59. {
  60. can[vec[i]][vec[j]] = 1;
  61. break;
  62. }
  63. }
  64. }
  65. }
  66. int bst = 0;
  67. do
  68. {
  69. int res = 0;
  70. VI ar;
  71. for(int i = 0; i < SZ(vec) -1;i +=2)
  72. {
  73. if(can[vec[i]][vec[i + 1]] ==-1)
  74. {
  75. ar.PB(vec[i]);
  76. ar.PB(vec[i + 1]);
  77. }
  78. else res++;
  79. }
  80. if(SZ(vec)% 2!=0)ar.PB(vec.back());
  81. bst = max(bst,res);
  82. for(auto x : ar)vv[res][x] = 1;
  83. }while(next_permutation(ALL(vec)));
  84. vec.clear();
  85. FOR(j,0,SZ(g[v]))
  86. {
  87. if(vv[bst][j] !=0)vec.PB(j);
  88. }
  89. ans+=bst ;
  90.  
  91. int mx = 0,id =-1;
  92. for(auto x : vec)
  93. {
  94. if(SZ(s[g[v][x]]) > mx)
  95. {
  96. mx = SZ(s[g[v][x]]);
  97. id = x;
  98. }
  99. }
  100. int idd = id == -1 ? -1 : g[v][id];
  101. for(auto x : vec)
  102. {
  103. if(x == id)continue;
  104. for(auto it : s[g[v][x]])s[idd].insert(it);
  105. }
  106. if(id!=-1)s[v].swap(s[idd]);
  107. }
  108. void dfs(int v,int p =-1)
  109. {
  110. if(clr[v])
  111. {
  112. s[v].insert(clr[v]);
  113. return ;
  114. }
  115. for(auto to : g[v])
  116. {
  117. if(to == p)continue;
  118. dfs(to,v);
  119. }
  120. merge(v,p);
  121.  
  122. }
  123. int main(){
  124. IOS;
  125.  
  126. int n,l;
  127. cin >> n >> l;
  128. rep(i,n - 1)
  129. {
  130. int a,b;
  131. cin >> a >> b;
  132. --a,--b;
  133. g[a].PB(b);
  134. g[b].PB(a);
  135. }
  136. rep(i,l)
  137. {
  138. int a,color;
  139. cin >> a >> color;
  140. --a;
  141. clr[a] = color;
  142. }
  143. if(n == 1)
  144. {
  145. cout << 0 ;
  146. return 0;
  147. }
  148. if(n == 2)
  149. {
  150. if(clr[0] == clr[1])cout << 1 ;
  151. else cout << 0 ;
  152. return 0;
  153. }
  154. FOR(i,0,n)
  155. {
  156. if(!clr[i])
  157. {
  158. dfs(i);
  159. cout << ans << '\n';
  160. return 0;
  161. }
  162. }
  163.  
  164.  
  165. }
  166.  
  167.  
RAW Paste Data