QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#865178	#1288. Tokens on the Tree	lc20110802	TL	1ms	12480kb	C++14	1.9kb	2025-01-21 15:51:29	2025-01-21 15:51:29

Judging History

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

[2025-01-21 15:51:29]
评测

测评结果：TL
用时：1ms
内存：12480kb

查看

[2025-01-21 15:51:29]
提交

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(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

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

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 12480kb

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: