QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#312265#7206. Triplesinsop90WA 4ms13984kbC++144.8kb2024-01-23 18:27:462024-01-23 18:27:46

Judging History

你现在查看的是最新测评结果

  • [2024-01-23 18:27:46]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:13984kb
  • [2024-01-23 18:27:46]
  • 提交

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 --;
		}
	}
}

Details

Tip: Click on the bar to expand more detailed information

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'