省略
省略
C++に変換後のコードはこちら
int N, A[2d5], B[2d5];
ll c[2d5];
int *es, **edge;
ll **dp;
int up[1d5];
ll res[1d5];
fenwick<int> f;
ll dfs1(int n, int b){
int i, k, t, u;
ll r = 0, tmp;
f.add(n,1);
up[n] = n;
rep(i,es[n]){
k = edge[n][i];
if(k==b) continue;
t = f.get(n);
tmp = dfs1(k,n);
tmp += (u = f.get(n) - t);
r += (dp[n][i] = tmp);
up[n] -= u;
}
return res[n] = r;
}
void dfs2(int n, int b, ll v){
int i, k;
if(b >= 0) res[n] += res[b] - v + up[n];
rep(i,es[n]){
k = edge[n][i];
if(k==b) continue;
dfs2(k,n,dp[n][i]);
}
}
{
rd(N,(A--,B--)(N-1));
rep(i,N-1) A[N-1+i] = B[i];
rep(i,N-1) B[N-1+i] = A[i];
wAdjEdge(N, 2*(N-1), A, B, c, &es, &edge, &dp);
f.walloc(N);
f.init(N);
dfs1(0, -1);
dfs2(0, -1, 0);
wtLn(res(N));
}
Current time: 2024年03月29日05時05分22秒
Last modified: 2019年09月01日00時50分54秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder
トップページに戻る
Logged in as: unknown user (not login)