QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#312213 | #7206. Triple | sinsop90 | RE | 2ms | 11740kb | C++14 | 4.2kb | 2024-01-23 16:33:58 | 2024-01-23 16:33:59 |
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;
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) {
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) {
F[now][0] ++;
if(son[now]) {
F[son[now]] = F[now] + 1;
dfs2(son[now], now);
F[now][0] += F[son[now]][0];
}
vector<int> P;
for(int i = head[now];i;i = e[i].pre) {
int v = e[i].v;
if(v == f || vis[v]) 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];
}
for(int i = (int)P.size() - 1, now = 0;i >= 0;i--) {
if(i <= dep[now]) break;
ans += (now * (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];
}
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) {
// 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];
}
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];
// 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];
init(v, now);
F[v] = o;
o += Ldep[v] + 1;
dfs2(v, now);
for(int j = mxdep;j >= 1;j--) vec[j] -= vec[j - 1];
}
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: 11740kb
input:
3 1 2 2 3 4 1 2 2 3 2 4
output:
4 18
result:
ok 2 tokens
Test #2:
score: -100
Runtime Error
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 ...