Submission #64790396

---

Source Code Expand

#include <bits/stdc++.h>
 
using namespace std;

const int MOD=1e9+7;

vector<int> get_dist(vector<vector<int>> & tree, int x){
	vector<int> ans(tree.size(),-1);
	queue<int> q;
	ans[x]=0;
	q.push(x);
	while(q.size()){
		int cur=q.front();
		q.pop();
		for(int y:tree[cur]){
			if(ans[y]==-1){
				ans[y]=ans[cur]+1;
				q.push(y);
			}
		}
	}
	return ans; 
	
	
}

vector<int> get_da(vector<vector<int>> & tree){
	vector<int> ans(tree.size());
	vector<int> temp=get_dist(tree,1);
	
	int d1=max_element(temp.begin(),temp.end())-temp.begin();
	
	vector<int> temp2=get_dist(tree,d1);
	
	int d2=max_element(temp2.begin(),temp2.end())-temp2.begin();
	
	vector<int> temp3=get_dist(tree,d2);
	
	for(int i=1; i<tree.size(); i++){
		ans[i]=max(temp2[i],temp3[i]);
	}
	return ans; 
	
	
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	int n1;
	cin>>n1; 
	vector<vector<int>> tree1(n1+1);
	for(int i=0; i<n1-1; i++){
		int x,y;
		cin>>x>>y;
		tree1[x].push_back(y);
		tree1[y].push_back(x);
		
	}
	
	int n2;
	cin>>n2; 
	vector<vector<int>> tree2(n2+1);
	for(int i=0; i<n2-1; i++){
		int x,y;
		cin>>x>>y;
		tree2[x].push_back(y);
		tree2[y].push_back(x);
		
	}
	
	vector<int> da = get_da(tree1), da2 = get_da(tree2);
	
	vector<int> v1(da.begin()+1,da.end()), v2(da2.begin()+1,da2.end());
	
	sort(v1.begin(),v1.end());
	sort(v2.begin(),v2.end());
	long long ans=0, tot=0;
	
	long long base=max(v1.back(),v2.back());
	
	for(int i=0,j=n2; i<n1; i++){
		long long x=v1[i];
		while(j&&v2[j-1]+v1[i]>=base){
			tot+=v2[--j];
			
		}
		
		ans+=base*j+(n2-j)*(x+1)+tot;
	}
	cout<<ans; 
	
	
	
	
    
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘std::vector<int> get_da(std::vector<std::vector<int> >&)’:
Main.cpp:39:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::vector<int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   39 |         for(int i=1; i<tree.size(); i++){
      |                      ~^~~~~~~~~~~~

Judge Result