abcdeffa's Blog

当局者迷，旁观者清。

0%

GMOJ S4211 【送你一颗圣诞树】

发表于 更新于

Description

给你一颗树 $T_0$，初始时 $T_0$ 只有一个节点。现在有 $n$ 个操作，第 $i$ 个操作是选出当前有的两棵树，把它们中的两个节点连接，成为一棵新树 $T_i$（旧树仍然存在），现在问你每棵树 $T_{1..n}$ 中两两节点之间的距离和，答案模 $(10^9 + 7)$。

Solution

吉老师的好题。

引用内容摘自官方题解，其中部分内容有删改。

可以分成两类询问：第一类用 $a, b, c$ 描述，表示询问第 $a$ 棵树中第 $b$ 个点和第 $c$ 个点的距离；第二种用 $a, b$ 描述，表示询问第 $a$ 棵树中所有点到第 $b$ 个点的距离和。可以发现如果可以得到这两类询问的答案，就可以递推出所有树的权值。
首先考虑第一类询问，如果用记忆搜的方式转化成子问题，可以发现这个搜索过程很类似线段树：中间一部分都已经记忆搜得到过了答案，只有两侧需要继续递归下去。显然这时最多递归 $n$ 次，时间复杂度是 $O(n)$。
然后我们考虑第二类询问，可以发现一个第二类询问可以转化为一个第一类询问和一个规模更小的第二类询问，即至多转化为 O(n) 个第一类询问，所以时间复杂度是 $O(n^2)$。
因为求一棵树的权值我们需要调用一次第二类询问，所以时间复杂度是 $O(n^3)$。

这题要注意取模，算答案的时候要先让大数模了再 加 / 乘，加完乘完还要再模，具体的可以参考 Code 部分。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <cstdio>
#include <cstring>
#include <unordered_map>
#define mod 1000000007
#define maxN 70
std::unordered_map<long long, std::unordered_map<long long, std::unordered_map<long long, long long> > > rem1;
std::unordered_map<long long, std::unordered_map<long long, long long> > rem2;
struct edge{ long long size, a, b, c, d, l; } f[maxN];
long long Ans[maxN];
long long to (long long T, long long x, long long y)
{
	if(rem1[T][x][y])
	{
		return rem1[T][x][y];
	}
	long long mid = f[f[T].a].size;
	if(x == y)
	{
		return 0;
	}
	if(x > y)
	{
		long long t = x;
		x = y;
		y = t;
	}
	if(x <= mid && y <= mid)
	{
		return rem1[T][x][y] = to(f[T].a, x, y);
	}
	else if(x > mid && y > mid)
	{
		return rem1[T][x][y] = to(f[T].b, x - mid, y - mid);
	}
	else
	{
		return rem1[T][x][y] = (((to(f[T].a, x, f[T].c) + f[T].l) % mod) + to(f[T].b, y - mid, f[T].d)) % mod;
	}
}
long long all (long long T, long long x)
{
	long long mid = f[f[T].a].size;
	if(rem2[T][x])
	{
		return rem2[T][x];
	}
	if(f[T].size == 1)
	{
		return 0;
	}
	if(x <= mid)
	{
		long long A = (f[f[T].b].size % mod) * (((f[T].l % mod) + to(f[T].a, x, f[T].c)) % mod) % mod;
		return rem2[T][x] = (((all(f[T].a, x) + all(f[T].b, f[T].d)) % mod) + A) % mod;
	}
	else
	{
		long long A = (f[f[T].a].size % mod) * (((f[T].l % mod) + to(f[T].b, x - mid, f[T].d)) % mod) % mod;
		return rem2[T][x] = ((all(f[T].b, x - mid) + all(f[T].a, f[T].c) % mod) + A) % mod;
	}
}
int main ()
{
	long long T = 0;
	scanf("%lld", &T);
	while(T--)
	{
		rem1.clear();
		rem2.clear();
		memset(f, 0, sizeof(f));
		memset(Ans, 0, sizeof(Ans));
		long long n = 0;
		scanf("%lld", &n);
		f[0].size = 1;
		for(long long i = 1;i <= n; i++)
		{
			long long A = 0, B = 0, C = 0, D = 0, L = 0;
			scanf("%lld %lld %lld %lld %lld", &A, &B, &C, &D, &L);
			C++, D++;
			f[i].a = A;
			f[i].b = B;
			f[i].c = C;
			f[i].d = D;
			f[i].l = L;
			f[i].size = f[A].size + f[B].size;
			long long AA = (Ans[A] + Ans[B]) % mod;
			long long BB = (f[A].size % mod) * (f[B].size % mod) % mod * (f[i].l % mod) % mod;
			long long CC = (f[A].size % mod) * all(B, D) % mod;
			long long DD = (f[B].size % mod) * all(A, C) % mod;
			Ans[i] = (((((AA + BB) % mod) + CC) % mod) + DD) % mod;
			printf("%lld\n", Ans[i]);
		}
	}
	return 0;
}