Codeforces Round #721 DIV2 D問題 (2250pt)
Problem description
省略
省略
C++に変換後のコードはこちら
//no-unlocked
int N, A[2d5], B[2d5];
graph g;
HLD hld;
ll res[2d5+1];
int sz[];
{
REP(rd_int()){
int x = 0, y = 0, z, fg;
rd(N,(A,B)(N-1));
g.setEdge(N,N-1,A,B);
hld.init(g);
rep(i,N+1) res[i] = 0;
g.SubTreeSize(0,sz);
rep[g.edge[0]](i,g.es[0]) res[0] += (ll)sz[i]*(sz[i]-1)/2;
res[1] = (ll) N * (N-1) / 2 - res[0];
rep(i,1,N){
fg = 0;
if(fg == 0 && abs(hld.depth(x) - hld.depth(i)) == hld.dist(x,i)){
fg = 1;
if(hld.depth(x) < hld.depth(i)) x = i;
}
if(fg == 0 && abs(hld.depth(y) - hld.depth(i)) == hld.dist(y,i)){
fg = 1;
if(hld.depth(y) < hld.depth(i)) y = i;
}
if(!fg || hld.lca(x,y) != 0) break;
if(y == 0){
z = hld.up(x, hld.depth(x)-1);
res[i+1] = (ll)sz[x] * (N-sz[z]);
} else {
res[i+1] = (ll)sz[x] * sz[y];
}
res[i] -= res[i+1];
}
wt(res(N+1));
}
}
Current time: 2024年04月24日08時17分25秒
Last modified: 2021年05月21日20時47分13秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF721 CF_DIV2_D
トップページに戻る
Logged in as: unknown user (not login)