ここ3か月で2回しかSRM出てない…。
https://community.topcoder.com/stat?c=problem_statement&pm=14462
問題
木を成す無向グラフSにおけるA(S)とは、Sの直径とおなじ距離を持つ2点の対の数を意味する。
ここで木を成す無向グラフTが与えられる。Tの部分グラフT'のうち、A(T')の最大値を求めよ。
解法
まず直径が偶数の部分グラフを作る場合を考える。
グラフの中心点vを定め、そこから距離dにある頂点数を数え上げたとき、中心点から見てC個の各子頂点のsubtreeの方向にN[0],N[1],N[2],...,N[C-1]個ずつあったとする。
その時、vを中心として距離dまでの頂点からなる部分グラフT'を考えると、となる。
よって、vを総当たりし、そこから各距離までの頂点数を各子頂点のSubtreeに対してDFSで数え上げれば、A(T')の最大値を求めることができる。
次に直径が奇数の場合を考える。
これは中心点vの代わりに2頂点u-vを結ぶ中心辺(?)を考え、同様にそこから距離dの頂点数を数え上げていけば同様にA(T')を列挙できる。
class TreeDiameters { public: int N; vector<int> E[1010]; int ma,md; int num[1010]; int sum[1010]; int count[1010]; void dfs(int cur,int pre,int d) { md=max(md,d); count[d]++; FORR(r,E[cur]) if(r!=pre) dfs(r,cur,d+1); } int getMax(vector <int> p) { int N=p.size()+1; int i,j; FOR(i,N) E[i].clear(); FOR(i,p.size()) E[i+1].push_back(p[i]),E[p[i]].push_back(i+1); ma=0; FOR(i,N) { ZERO(num); ZERO(sum); FORR(r,E[i]) { md=0; dfs(r,i,1); for(j=0;j<=md;j++) { sum[j] += num[j]*count[j]; ma=max(ma,sum[j]); num[j] += count[j]; count[j]=0; } } } FOR(i,N) FORR(r,E[i]) if(r>i) { ZERO(num); ZERO(sum); md=0; dfs(i,r,0); for(j=0;j<=md;j++) num[j]=count[j], count[j]=0; md=0; dfs(r,i,0); for(j=0;j<=md;j++) ma=max(ma,num[j]*count[j]),count[j]=0; } return ma; } }
まとめ
直径が奇数の場合は、中心を点でなく辺でとるというテクは覚えておいたほうがいいね。