これは自力で解けた。
https://community.topcoder.com/stat?c=problem_statement&pm=14367
問題
木を成す無向グラフが与えられる。
ここから1つの連結した部分グラフを取ることを考える。
この部分グラフの直径を成す頂点対が1つになるようなグラフは何通りあるか。
解法
まず1点しかない部分グラフは常に条件を満たす。
以後2点以上ある場合を考える。
D(u,v)を頂点u,v間の最短距離とする。
グラフの直径を成す2点(u,v)を総当たりしよう。
u',v'を以下のように定める。
- D(u,v)が偶数の場合、u'もv'もu,vの中点。
- D(u,v)が奇数の場合、D(u,u')=D(v,v')=(D(u,v)-1)/2となる点。すなわちu-vをつないだ頂点群のうち中央の2点
u',v'からDFSで各頂点xを探索し、条件を満たす頂点の残し方を列挙しよう。
- xがu-vの最短経路上にあるなら必ず残す。
- xを残すと直径がD(u,v)以上になりうる、すなわちmax(D(x,u'),D(x,v'))≧(D(u,v)-1)/2ならば、xは消す一択。
- それ以外の場合、xは消しても残しても良い。消す場合が1通り、残す場合は(u'やv'から見て遠い方の)各頂点の組み合わせの掛算の分だけ組み合わせがある。
vector<int> E[301]; int num[301][301]; int mat[301][301]; ll mo=1000000007; class BearUniqueDiameter { public: int N; ll dfs(int cur,int pre,int left,int u,int v) { if(left<0) return 1; ll ret=1; int canerase = (mat[cur][u]+mat[cur][v]>mat[u][v]); FORR(e,E[cur]) if(e!=pre) (ret *= dfs(e,cur,left-1,u,v))%=mo; return ret+canerase; } int countSubtrees(vector <int> a, vector <int> b) { int x,y,z,i; N=a.size()+1; FOR(x,N) FOR(y,N) mat[x][y]=(x!=y)*999; FOR(i,N-1) mat[a[i]][b[i]]=mat[b[i]][a[i]]=1; FOR(z,N) FOR(x,N) FOR(y,N) mat[x][y]=min(mat[x][y],mat[x][z]+mat[z][y]); FOR(i,N) E[i].clear(); FOR(i,N-1) E[a[i]].push_back(b[i]),E[b[i]].push_back(a[i]); ll ret=N; FOR(y,N) FOR(x,y) { int d=mat[x][y]; int u=-2,v=-2,i; FOR(i,N) { if(d%2==0 && mat[x][i]==mat[y][i] && mat[x][i]==d/2) u=i,v=-1; if(d%2==1 && mat[x][i]==d/2 && mat[y][i]==d/2+1) u=i; if(d%2==1 && mat[x][i]==d/2+1 && mat[y][i]==d/2) v=i; } if(v==-1) ret += dfs(u,-1,d/2-1,x,y); else ret += dfs(u,v,d/2-1,x,y)*dfs(v,u,d/2-1,x,y)%mo; } return ret%mo; } }
まとめ
ちょっと悩んだけど、コードはそんなに複雑ではないね。