fork(17) download
copy 
  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
comments (?)
stdin
copy 
5 2
1 3 3 5
3 2 4 1
1 3
stdout
copy 
3 2
https://ideone.com/lbqZyK
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!