CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
最后十六秒绝杀过了 1002，捡了件衣服~
Diversity
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 9;
vector<vector<int>> g;
int t, n, a[N][2];
ll f[N][2];
void dp(int u, int fa)
{
f[u][0] = f[u][1] = 0;
for (auto to : g[u])
if (to != fa)
{
dp(to, u);
f[u][0] += max(abs(a[u][0] - a[to][0]) + f[to][0], abs(a[u][0] - a[to][1]) + f[to][1]);
f[u][1] += max(abs(a[u][1] - a[to][0]) + f[to][0], abs(a[u][1] - a[to][1]) + f[to][1]);
}
}
int main()
{
for (scanf("%d", &t); t--;)
{
scanf("%d", &n);
g.assign(n, vector<int>());
for (int i = 1, u, v; i < n; ++i)
{
scanf("%d%d", &u, &v);
--u, --v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 0; i < n; ++i)
scanf("%d%d", &a[i][0], &a[i][1]);
dp(0, -1);
printf("%lld\n", max(f[0][0], f[0][1]));
}
}
Transformation
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll sgn(ll a)
{
return a < 0 ? -1 : a > 0 ? 1 : 0;
}
int main()
{
ll t, a, b, c, d;
for (scanf("%lld", &t); t--;)
{
scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
if (a == c && b == d)
{
printf("Yes\n\n");
continue;
}
if (a == b || c == d)
{
printf("No\n");
continue;
}
if (a < b && c > d || a > b && c < d)
{
printf("No\n");
continue;
}
ll x = abs(a - b), y = abs(c - d), o = 0;
for (;; x <<= 1, ++o)
{
if (x > y)
o = -1;
if (x >= y)
break;
}
if (o < 0)
{
printf("No\n");
continue;
}
ll u = d - b, v = b - a;
if (u % v)
{
printf("No\n");
continue;
}
u /= v;
string s;
for (int i = 0; i < o; ++i)
s += u % 2 ? 'A' : 'B', u /= 2;
for (int i = 0; i < s.size(); ++i)
{
if (s[i] == 'A')
b = 2 * b - a;
else
a = 2 * a - b;
}
if (a == c && b == d)
{
printf("Yes\n");
cout << s << '\n';
}
else
puts("No");
}
}
Quasi Binary Search Tree
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Mod
{
const ll M, SM;
Mod(ll M) : M(M), SM(sqrt(M) + 0.5) {}
ll qadd(ll &a, ll b) const { return a += b, a < M ? a : a - M; } //假如a和b都已经在同余系内，就不必取模了，取模运算耗时很高
ll add(ll a, ll b) const { return qadd(a = (a + b) % M, M); } //考虑a和b不在同余系内甚至为负数的情况
ll mul(ll a, ll b) const { return add(a * b, M); }
//ll mul(ll a, ll b) const { return add(a * b, -M * ll((long double)a / M * b)); }
ll pow(ll a, ll b) const
{
ll r = 1;
for (a = add(a, M); b; b >>= 1, a = mul(a, a))
if (b & 1)
r = mul(r, a);
return r;
}
ll inv(ll a) const { return pow(a, M - 2); } //要求M为素数
/*
ll inv(ll a) const //模m下a的乘法逆元，不存在返回-1（m为素数时a不为0必有逆元）
{
ll x, y, d = gcd(a, M, x, y);
return d == 1 ? add(x, M) : -1; //return pow(a, phi(M) - 1);
}
vector<ll> sol(ll a, ll b) const //解同余方程，返回ax=b(mod M)循环节内所有解
{
vector<ll> ans;
ll x, y, d = gcd(a, M, x, y);
if (b % d)
return ans;
ans.push_back(mul((b / d) % (M / d), x));
for (ll i = 1; i < d; ++i)
ans.push_back(add(ans.back(), M / d));
return ans;
}
*/
ll log(ll a, ll b) const
{
unordered_map<ll, ll> x;
for (ll i = 0, e = 1; i <= SM; ++i, e = mul(e, a))
if (!x.count(e))
x[e] = i;
for (ll i = 0, v = inv(pow(a, SM)); i <= SM; ++i, b = mul(b, v))
if (x.count(b))
return i * SM + x[b];
return -1;
}
} M(1e9 + 7);
const int N = 1e5 + 9;
int t, n, l[N], r[N], fa[N], siz[N], mi[N], ans[N];
void dfs(int u)
{
siz[u] = 1;
mi[u] = u;
if (l[u])
dfs(l[u]), siz[u] += siz[l[u]], mi[u] = min(mi[u], mi[l[u]]);
if (r[u])
dfs(r[u]), siz[u] += siz[r[u]], mi[u] = min(mi[u], mi[r[u]]);
}
void dp(int u, int &cnt)
{
if (!l[u])
{
if (!r[u])
{
ans[u] = ++cnt;
return;
}
if (mi[r[u]] < u)
dp(r[u], cnt), ans[u] = ++cnt;
else
ans[u] = ++cnt, dp(r[u], cnt);
return;
}
if (!r[u])
{
if (mi[l[u]] < u)
dp(l[u], cnt), ans[u] = ++cnt;
else
ans[u] = ++cnt, dp(l[u], cnt);
return;
}
if (u < mi[l[u]] && u < mi[r[u]] && siz[l[u]] != siz[r[u]])
{
vector<int> v{siz[l[u]], siz[r[u]]};
sort(v.begin(), v.end());
for (int i = 0; i < 1; ++i)
{
if (v[i] == siz[l[u]])
dp(l[u], cnt);
else if (v[i] == siz[r[u]])
dp(r[u], cnt);
}
ans[u] = ++cnt;
for (int i = 1; i < 2; ++i)
{
if (v[i] == siz[l[u]])
dp(l[u], cnt);
else if (v[i] == siz[r[u]])
dp(r[u], cnt);
}
return;
}
vector<int> v{mi[l[u]], mi[r[u]]};
sort(v.begin(), v.end());
for (int i = 0; i < 1; ++i)
{
if (v[i] == mi[l[u]])
dp(l[u], cnt);
else if (v[i] == mi[r[u]])
dp(r[u], cnt);
}
ans[u] = ++cnt;
for (int i = 1; i < 2; ++i)
{
if (v[i] == mi[l[u]])
dp(l[u], cnt);
else if (v[i] == mi[r[u]])
dp(r[u], cnt);
}
}
int main()
{
for (scanf("%d", &t); t--;)
{
scanf("%d", &n);
fill(fa + 1, fa + n + 1, 0);
fill(l + 1, l + n + 1, 0);
fill(r + 1, r + n + 1, 0);
fill(ans + 1, ans + n + 1, 0);
for (int i = 1; i <= n; ++i)
{
scanf("%d%d", &l[i], &r[i]);
fa[l[i]] = fa[r[i]] = i;
}
for (int i = 1, cnt = 0; i <= n; ++i)
if (!fa[i])
{
dfs(i);
dp(i, cnt);
break;
}
ll an = 0;
for (int i = 1; i <= n; ++i)
an = M.add(an, M.mul(ans[i] ^ i, M.pow(233, i)));
printf("%lld\n", an);
}
}