QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#865176#1288. Tokens on the Treelc20110802TL 2ms11292kbC++141.8kb2025-01-21 15:50:502025-01-21 15:50:51

Judging History

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

  • [2025-01-21 15:50:51]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:11292kb
  • [2025-01-21 15:50:50]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#define S(X, Y) (((X) + (Y)) * ((Y) - (X) + 1) / 2) % Mod
using namespace std;

const int N = 2e5 + 10, Mod = 1e9 + 7;
int n, fa[N], nxt[N], siz[N], ans;
pair<int, int> Max;
vector<int> g[N];

void cal(int u, int pre){
	int fir = 0, sec = 0, tmp;
	for(int v : g[u]) if(v != pre){
		tmp = siz[v];
		if(tmp >= fir) swap(fir, tmp);
		if(tmp >= sec) swap(sec, tmp);
	}
	nxt[fir] = max(nxt[fir], sec);
	nxt[sec] = max(nxt[sec], fir);
	for(int v : g[u]) if(v != pre)
		cal(v, u);
	return ;
};

void fun(int u, int pre){
	int tmp = S(max(n - siz[pre] + 1, Max.first + 1), n - siz[u]);
	tmp = 2 * tmp % Mod * S(1, siz[u]) % Mod; ans = (ans + tmp) % Mod;
	for(int v : g[u]) if(v != pre) fun(v, u);
	return ;
};

void dfs(int u, int pre){
	siz[u] = 1;
	for(int v : g[u]) if(v != pre)
		dfs(v, u), siz[u] += siz[v];
	return ;
};

void init(){
	Max = make_pair(0, 0);
	for(int i = 0; i <= n + 5; i++)
		siz[i] = fa[i] = nxt[i] = 0;
	ans = 0;
	for(int i = 0; i < N; i++) g[i].clear();
}

void solve(){
	init();

	cin >> n;
	for(int i = 2; i <= n; i++){
		cin >> fa[i];
		g[i].push_back(fa[i]);
		g[fa[i]].push_back(i);
	}
	for(int i = n; i >= 1; i--) siz[fa[i]] += ++siz[i];
	int G = 1, H = 0;

	find_G:;
	for(int v : g[G]) if(v != H)
		if(siz[v] > siz[1] / 2){
			H = G, G = v; goto find_G;}

	dfs(G, 0); siz[G]--;

	for(int v : g[G]) Max = max(Max, make_pair(siz[v], v));

	ans = S(1, Max.first) * S(1, Max.first) % Mod;

	cal(G, Max.second);
	cal(Max.second, G);
	for(int i = Max.first; i >= 1; i--){
		nxt[i] = max(nxt[i], nxt[i + 1]);
		if(nxt[i] + 1 <= Max.first)
			ans = (ans + i * S(nxt[i] + 1, Max.first)) % Mod;
	}

	for(int v : g[G]) fun(v, G);

	cout << ans << '\n';
	return ;
}

signed main(){
	int T; cin >> T;
	while(T--) solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 11292kb

input:

2
5
1 2 3 3
10
1 2 3 4 3 6 3 8 2

output:

71
989

result:

ok 2 tokens

Test #2:

score: -100
Time Limit Exceeded

input:

33327
10
1 2 3 4 5 2 7 8 2
7
1 2 3 4 5 2
8
1 2 3 4 5 3 1
2
1
7
1 2 3 3 3 1
5
1 2 2 1
5
1 2 3 1
2
1
4
1 2 2
8
1 2 3 4 5 5 4
9
1 2 3 1 5 6 7 8
5
1 1 3 4
8
1 2 3 3 5 5 5
8
1 2 2 2 1 6 1
6
1 2 3 2 5
7
1 2 3 4 3 2
5
1 2 3 3
4
1 1 1
6
1 1 3 4 4
3
1 2
10
1 2 1 4 5 5 7 7 9
2
1
3
1 2
6
1 1 3 4 5
7
1 2 3 1 5 ...

output:

981
253
421
2
251
71
70
2
31
423
660
70
419
419
141
255
71
31
141
10
997
2
10
140
252
10
71
2
2
675
423
1007
71
70
140
429
30
667
10
945
655
70
661
10
10
70
31
255
141
71
255
669
30
252
2
30
419
255
661
427
10
421
2
659
141
993
30
141
417
10
2
423
141
30
667
675
417
71
421
255
10
140
675
2
30
2
31
3...

result: