QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#312258 | #7206. Triple | sinsop90 | WA | 3ms | 13764kb | C++14 | 4.8kb | 2024-01-23 18:19:50 | 2024-01-23 18:19:51 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 5, maxm = 2e6 + 5;
int n, ans, head[maxn], tot, DP[maxn], sz[maxn], *F[maxn], buc[maxm], SZ, vis[maxn], rt, dep[maxn], mxdep, Ldep[maxn], son[maxn];
int *o = buc, nowSZ;
vector<int> vec, tem;
struct edge {
int v, pre;
}e[maxn << 1];
void add(int u, int v) {
e[++ tot].v = v;
e[tot].pre = head[u];
head[u] = tot;
}
void getsz(int now, int f) {
SZ ++;
for(int i = head[now];i;i = e[i].pre) {
int v = e[i].v;
if(v == f || vis[v]) continue;
getsz(v, now);
}
}
void getrt(int now, int f) {
sz[now] = 1, DP[now] = 0;
for(int i = head[now];i;i = e[i].pre) {
int v = e[i].v;
if(v == f || vis[v]) continue;
getrt(v, now);
sz[now] += sz[v];
DP[now] = max(DP[now], sz[v]);
}
DP[now] = max(DP[now], SZ - 1 - DP[now]);
if(rt == -1 || DP[now] < DP[rt]) rt = now;
}
void dfs(int now, int f) {
// cout << now << " " << f << '\n';
dep[now] = dep[f] + 1;
mxdep = max(mxdep, dep[now]);
if(mxdep >= tem.size()) tem.resize(mxdep + 1);
tem[dep[now]] ++;
for(int i = head[now];i;i = e[i].pre) {
int v = e[i].v;
if(v == f || vis[v]) continue;
dfs(v, now);
}
}
void init(int now, int f) {
Ldep[now] = son[now] = 0;
for(int i = head[now];i;i = e[i].pre) {
int v = e[i].v;
if(v == f || vis[v]) continue;
init(v, now);
if(Ldep[v] + 1 > Ldep[now]) son[now] = v, Ldep[now] = Ldep[v] + 1;
}
}
void dfs2(int now, int f) {
// cout << now << " " << f << '\n';
ans += (dep[now] - 1) * (nowSZ - SZ - 1);
if(son[now]) {
F[son[now]] = F[now] + 1;
dfs2(son[now], now);
F[now][0] += F[son[now]][0];
}
vector<int> P(1, 1);
for(int i = head[now];i;i = e[i].pre) {
int v = e[i].v;
if(v == f || vis[v] || v == son[now]) continue;
o += Ldep[now] + 1;
F[v] = o;
dfs2(v, now);
if(Ldep[v] + 2 > P.size()) P.resize(Ldep[v] + 2);
for(int j = 0;j <= Ldep[v];j++) P[j + 1] += F[v][j];
}
// cout << now << " " << P.size() << "\n";
for(int i = (int)P.size() - 1, sum = 0;i >= 0;i--) {
if(i <= dep[now]) break;
// cout << now << " " << sum << '\n';
ans += sum * P[i] * vec[i - dep[now] - 1] * 2;
ans += (sum * (F[now][i] - F[now][i + 1]) + P[i] * F[now][i + 1] + P[i] * (F[now][i] - F[now][i + 1])) * 2 * vec[i - dep[now] - 1];
sum += P[i];
}
for(int i = (int)P.size() - 2;i >= 0;i--) P[i] += P[i + 1];
for(int i = 0;i < P.size();i++) F[now][i] += P[i];
vector<int>().swap(P);
}
void solve(int now) {
nowSZ = SZ;
// cout << now << "!!!\n";
vector<int> D;
vec.clear();
vis[now] = 1, dep[now] = 0, mxdep = 0;
for(int i = head[now];i;i = e[i].pre) {
int v = e[i].v;
if(vis[v]) continue;
tem.clear();
dfs(v, now);
// cout << now << " " << v << " " << mxdep << " " << '\n';
vec.resize(mxdep + 1), tem.resize(mxdep + 1), D.resize(mxdep + 1);
for(int j = mxdep, now = 0, now2 = 0;j >= 1;j--) {
D[j] += tem[j] * now + vec[j] * now2 + tem[j] * vec[j];
// cout << vec[j] << " " << tem[j] << '\n';
now += vec[j], now2 += tem[j];
}
// cout << v << " " << D[1] << '\n';
for(int j = 0;j <= mxdep;j++) vec[j] += tem[j];
// cout << "!!!\n";
}
for(int j = 1;j <= mxdep;j++) D[j] *= 2;
if(vec.size()) vec[0] ++;
for(int j = 1;j <= mxdep;j++) vec[j] += vec[j - 1];
for(int j = 1;j <= mxdep;j++) ans += vec[j - 1] * D[j];
for(int j = mxdep;j >= 1;j--) vec[j] -= vec[j - 1];
// cout << ans << '\n';
// for(int x : vec) cout << x << " ";
// cout << '\n';
for(int i = head[now];i;i = e[i].pre) {
int v = e[i].v;
if(vis[v]) continue;
tem.clear();
dfs(v, now);
tem.resize(mxdep + 1);
for(int j = 0;j <= mxdep;j++) vec[j] -= tem[j];
for(int j = 1;j <= mxdep;j++) vec[j] += vec[j - 1];
SZ = 0;
getsz(v, now);
init(v, now);
F[v] = o;
o += Ldep[v] + 1;
dfs2(v, now);
for(int j = Ldep[v], sum = 0;j >= 0;j--) {
// cout << v << " " << j << " " << F[v][j] << "\n";
ans += 2 * sum * F[v][j];
sum += F[v][j];
}
for(int j = mxdep;j >= 1;j--) vec[j] -= vec[j - 1];
}
// cout << ans << "\n";
for(int i = head[now];i;i = e[i].pre) {
int v = e[i].v;
if(vis[v]) continue;
rt = -1, SZ = 0;
getsz(v, now);
getrt(v, now);
solve(rt);
}
}
void solve() {
for(int i = 1, u, v;i < n;i++) {
cin >> u >> v;
add(u, v), add(v, u);
}
rt = -1, SZ = 0;
getsz(1, 0);
getrt(1, 0);
// cout << DP[1] << " " << DP[2] << " " << DP[3] << " " << SZ << '\n';
solve(rt);
cout << n * (n - 1) * (n - 2) - ans << '\n';
}
signed main() {
// ios::sync_with_stdio(0);
// cin.tie(0), cout.tie(0);
while(cin >> n) {
solve();
ans = tot = rt = SZ = 0;
for(int i = 1;i <= n;i++) head[i] = DP[i] = sz[i] = son[i] = dep[i] = Ldep[i] = vis[i] = 0;
vec.clear(), tem.clear();
while(1) {
(*o) = 0;
if(o == buc) break;
o --;
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 12008kb
input:
3 1 2 2 3 4 1 2 2 3 2 4
output:
4 18
result:
ok 2 tokens
Test #2:
score: -100
Wrong Answer
time: 3ms
memory: 13764kb
input:
5 4 1 3 4 2 5 3 5 5 5 4 3 4 4 1 1 2 5 4 5 4 1 3 2 4 3 5 1 3 4 3 2 4 5 1 5 4 1 4 2 5 4 5 3 5 1 4 5 2 3 5 3 1 5 5 3 3 4 2 1 5 2 5 5 1 5 4 1 2 2 3 5 5 2 2 4 1 3 1 2 5 1 3 2 4 5 4 3 5 5 4 1 2 4 5 4 3 1 5 1 5 3 1 1 2 4 2 5 2 5 4 2 3 4 4 1 5 5 1 4 2 2 1 1 3 5 4 2 3 4 1 4 5 2 5 3 1 3 2 3 5 4 1 5 3 4 2 5 4 ...
output:
36 44 44 36 44 36 36 36 44 36 44 44 44 44 44 44 36 36 44 36 36 44 44 44 36 44 36 36 44 44 36 44 44 36 44 48 44 36 36 36 36 36 48 36 44 44 36 44 48 36 36 44 36 44 44 44 36 36 36 36 44 44 44 44 36 36 44 48 36 44 36 36 44 44 44 36 44 44 44 44 44 48 44 36 36 36 36 48 36 44 44 36 44 44 44 36 36 44 44 36 ...
result:
wrong answer 1st words differ - expected: '40', found: '36'