Codeforces #614 Div1 C. Xenon's Attack on the Gangs

ここまではいつもより簡単寄り。
https://codeforces.com/contest/1292/problem/C

問題

N頂点の木を成す無向グラフが与えられる。
各辺に0～N-2の整数を1つずつ振ろう。

2頂点(u,v)に対し、その間のパス上の値のMex値の総和の最大値を求めよ。

解法

長さLのパスがあるとき、その間を0～(L-1)の値を割り当てれば、両端の先にある頂点の対に対し、Mex値Lが確保できる。
ここから、各長さのパスを列挙し、両端の先にある頂点対の積の数の最大となるものを選ぼう。
選ぶパスは直前の長さのパスを含み徐々に長くなる向きにしか増えない点に注意。

int N;
vector<int> E[3030];
int num[3030][3030];
int L[3030][3030];
int P[3030][3030];

ll dp[3030][3030];
vector<pair<int,int>> C[3030];

int dfs(int cur,int pre,int id) {
	num[id][cur]=1;
	P[id][cur]=pre;
	if(cur!=pre) {
		L[id][cur]=L[id][pre]+1;
		C[L[id][cur]].push_back({id,cur});
	}
	
	
	FORR(e,E[cur]) if(e!=pre) num[id][cur]+=dfs(e,cur,id);
	return num[id][cur];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	FOR(i,N) dfs(i,i,i);
	
	ll ma=0;
	FORR(c,C[1]) {
		x=c.first,y=c.second;
		dp[x][y]=num[x][y]*num[y][x];
		ma=max(ma,dp[x][y]);
	}
	for(i=2;i<=3000;i++) FORR(c,C[i]) {
		x=c.first,y=c.second;
		dp[x][y]=max(dp[x][y],dp[x][P[x][y]]+num[x][y]*num[y][x]);
		dp[x][y]=max(dp[x][y],dp[P[y][x]][y]+num[x][y]*num[y][x]);
		ma=max(ma,dp[x][y]);
	}
	cout<<ma<<endl;
}

まとめ

今回の問題名なんなんだ。