QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#312265 | #7206. Triple | sinsop90 | WA | 4ms | 13984kb | C++14 | 4.8kb | 2024-01-23 18:27:46 | 2024-01-23 18:27:46 |
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;
}
}
/*
5
4 1
3 4
2 5
3 5
5
5 4
3 4
4 1
1 2
*/
void dfs2(int now, int f) {
// cout << now << " " << f << '\n';
ans += dep[now] * (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, ans -= D[j] * (2 * j - 1);
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 --;
}
}
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 11672kb
input:
3 1 2 2 3 4 1 2 2 3 2 4
output:
4 18
result:
ok 2 tokens
Test #2:
score: 0
Accepted
time: 0ms
memory: 13984kb
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:
40 44 44 40 44 40 40 40 44 40 44 44 44 44 44 44 40 40 44 40 40 44 44 44 40 44 40 40 44 44 40 44 44 40 44 48 44 40 40 40 40 40 48 40 44 44 40 44 48 40 40 44 40 44 44 44 40 40 40 40 44 44 44 44 40 40 44 48 40 44 40 40 44 44 44 40 44 44 44 44 44 48 44 40 40 40 40 48 40 44 44 40 44 44 44 40 40 44 44 40 ...
result:
ok 200 tokens
Test #3:
score: -100
Wrong Answer
time: 4ms
memory: 9728kb
input:
6 3 5 2 5 6 1 6 3 4 6 6 1 2 4 1 6 2 2 3 5 6 6 3 4 6 3 1 2 1 5 4 1 6 1 2 6 3 1 3 1 4 4 5 6 2 1 6 2 5 2 3 5 4 2 6 4 6 2 3 6 1 3 5 1 5 6 5 4 6 2 6 1 1 5 3 4 6 2 1 6 4 1 4 2 5 3 6 6 1 6 1 3 5 3 6 2 2 4 6 5 3 5 4 1 3 6 4 2 3 6 4 5 1 3 2 4 3 2 6 4 6 1 4 3 6 6 1 1 2 1 5 6 6 4 1 4 4 5 3 4 3 2 6 6 3 2 3 4 6 ...
output:
81 88 81 88 95 71 71 71 71 83 83 95 95 81 88 95 88 88 88 71 88 88 81 71 95 71 95 95 71 81 88 88 88 81 83 88 95 88 88 88 81 88 71 95 88 71 95 71 71 83 88 71 83 88 95 71 95 83 95 71 95 71 95 88 83 88 71 88 81 95 88 88 81 71 88 88 81 81 83 88 83 88 88 83 88 71 71 71 81 81 71 88 83 88 71 88 88 88 88 71 ...
result:
wrong answer 1st words differ - expected: '86', found: '81'