Submission #4353107


Source Code Expand

Copy
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/
const llint mod=1000000007;
const llint big=2.19e18+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
int n;
vector<vector<int>>go;
vector<int>cho;//子の最大深さ
int dfs(int ter,int per){
	//子の最大深さを返します
	int ret=0;
	for(auto it:go[ter]){
		if(it==per){continue;}
		maxeq(ret,dfs(it,ter)+1);
	}
	cho[ter]=ret;
	return ret;
}
void efs(int ter,int per,int uef){
	pair<int,int>sai=mp(uef+1,-1);
	pair<int,int>nib=mp(-1,-1);
	for(auto it:go[ter]){
		if(it==per){continue;}
		maxeq(nib,mp(cho[it]+1,it));
		if(sai<nib){swap(nib,sai);}
	}
	for(auto it:go[ter]){
		if(it==per){continue;}
		if(it==sai.sec){efs(it,ter,nib.fir);}
		else{efs(it,ter,sai.fir);}
	}
	cho[ter]=sai.fir;
}
vector<llint> solve(void){
	int i,n;cin>>n;
	go.clear();go.resize(n);
	for(i=1;i<n;i++){
		int p,q;cin>>p>>q;p--;q--;
		go[p].pub(q);
		go[q].pub(p);
	}
	cho.clear();
	cho.resize(n);
	//cerr<<"de ok"<<endl;
	dfs(0,-1);
	//cerr<<"de ok"<<endl;
	efs(0,-1,-1);
	vector<llint>ans(n);
	for(i=0;i<n;i++){ans[cho[i]]++;}
	//cerr<<"de ok"<<endl;
	return ans;
}

int main(void){
	cout<<fixed<<setprecision(20);
	cin.tie(0);ios::sync_with_stdio(false);
	//this is easy 600pot problem
	auto Anum=solve();llint n=Anum.size();
	auto Bnum=solve();llint m=Bnum.size();
	if(n<m){swap(Anum,Bnum);swap(n,m);}
	llint i,j,ans=0,mto=0;
	for(i=0;i<n;i++){if(Anum[i]>0){maxeq(mto,i);}}
	for(i=0;i<m;i++){if(Bnum[i]>0){maxeq(mto,i);}}
	vector<llint>Arui(n+1);
	for(i=1;i<=n;i++){Arui[i]=Arui[i-1]+Anum[i-1];}
	vector<llint>Apot(n+1);
	for(i=n-1;i>=0;i--){Apot[i]=Apot[i+1]+Anum[i]*i;}
	//for(i=0;i<n;i++){cerr<<Anum[i]<<endl;}
	//for(i=0;i<m;i++){cerr<<Bnum[i]<<endl;}
	for(i=0;i<m;i++){
		int x=max(0LL,mto-i-1);
		ans+=Bnum[i]*Arui[x]*mto;
		ans+=Bnum[i]*((n-Arui[x])*(i+1)+Apot[x]);
	}
	cout<<ans<<endl;
	return 0;
}

Submission Info

Submission Time
Task B - Bonsai Grafting
User WA_TLE
Language C++14 (GCC 5.4.1)
Score 700
Code Size 3374 Byte
Status
Exec Time 90 ms
Memory 14976 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 01.txt, 02.txt
All 700 / 700 01.txt, 02.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt
Case Name Status Exec Time Memory
01.txt 1 ms 256 KB
02.txt 1 ms 256 KB
11.txt 1 ms 256 KB
12.txt 1 ms 256 KB
13.txt 1 ms 256 KB
14.txt 1 ms 256 KB
15.txt 1 ms 256 KB
16.txt 1 ms 256 KB
17.txt 1 ms 256 KB
18.txt 1 ms 256 KB
19.txt 1 ms 256 KB
20.txt 1 ms 256 KB
21.txt 81 ms 9344 KB
22.txt 83 ms 11008 KB
23.txt 78 ms 9472 KB
24.txt 87 ms 13824 KB
25.txt 69 ms 9600 KB
26.txt 79 ms 9600 KB
27.txt 82 ms 13952 KB
28.txt 85 ms 9344 KB
29.txt 88 ms 13824 KB
30.txt 90 ms 14720 KB
31.txt 76 ms 9344 KB
32.txt 76 ms 9728 KB
33.txt 84 ms 9472 KB
34.txt 88 ms 14976 KB
35.txt 73 ms 9728 KB
36.txt 79 ms 9600 KB
37.txt 81 ms 12672 KB
38.txt 85 ms 9344 KB
39.txt 88 ms 13184 KB
40.txt 82 ms 13568 KB
41.txt 44 ms 8576 KB
42.txt 47 ms 8576 KB
43.txt 45 ms 8576 KB
44.txt 47 ms 8576 KB
45.txt 38 ms 8832 KB
46.txt 37 ms 8832 KB
47.txt 48 ms 13824 KB
48.txt 49 ms 8576 KB
49.txt 47 ms 11520 KB
50.txt 51 ms 11520 KB