CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
最后十六秒绝杀过了 1002，捡了件衣服~
Diversity
#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
#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
#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);
}
}