fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int getRoot(int node,vector<int> &P){
  5. while(P[node]!=node){
  6. node=P[node];
  7. }
  8. return node;
  9. }
  10.  
  11. int find(int n1,int n2,vector<int> &P){
  12. return getRoot(n1,P)==getRoot(n2,P);
  13. }
  14.  
  15. void unioN(int n1,int n2,vector<int> &P,vector<int> &size,int &maxi){
  16. if(find(n1,n2,P)==1)return;
  17. int rootN1=getRoot(n1,P);
  18. int rootN2=getRoot(n2,P);
  19. int sizeN1=size[rootN1];
  20. int sizeN2=size[rootN2];
  21. if(sizeN1>sizeN2){
  22. P[rootN2]=rootN1;
  23. size[rootN1]+=size[rootN2];
  24. maxi=max(maxi,size[rootN1]);
  25. }
  26. else{
  27. P[rootN1]=rootN2;
  28. size[rootN2]+=size[rootN1];
  29. maxi=max(maxi,size[rootN2]);
  30. }
  31. return;
  32. }
  33.  
  34. vector<int> solve(int A, vector<int> &B, vector<int> &C, vector<int> &D) {
  35. map<int,bool> ntMe;
  36. for(int i=0;i<D.size();i++){
  37. ntMe[D[i]-1]=true;
  38. }
  39. int maxi=1;
  40. vector<int> parent(A+1),size(A+1);
  41. for(int i=0;i<=A;i++){
  42. parent[i]=i;
  43. size[i]=1;
  44. }
  45.  
  46. for(int i=0;i<B.size();i++){
  47. if(!ntMe[i]){
  48. unioN(B[i],C[i],parent,size,maxi);
  49. }
  50. }
  51. vector<int> ans(D.size());
  52. for(int i=D.size()-1;i>=0;i--){
  53. ans[i]=maxi;
  54. unioN(B[D[i]-1],C[D[i]-1],parent,size,maxi);
  55. }
  56. return ans;
  57. }
  58.  
  59.  
  60. int main() {
  61. int a,q;
  62. cin>>a>>q;
  63. vector<int> B(a-1),C(a-1),D(q);
  64. for(int i=0;i<a-1;i++){
  65. cin>>B[i];
  66. }
  67. for(int i=0;i<a-1;i++){
  68. cin>>C[i];
  69. }
  70. for(int i=0;i<q;i++){
  71. cin>>D[i];
  72. }
  73.  
  74. vector<int> ans;
  75. ans=solve(a,B,C,D);
  76. for(int i=0;i<ans.size();i++){
  77. cout<<ans[i]<<" ";
  78. }
  79. return 0;
  80. }
Success #stdin #stdout 0s 4340KB
stdin
5 2
1 3 3 5
3 2 4 1
1 3 
stdout
3 2