又双叒叕垫底了。
rank 11，T1 90，T2 12，T3 5，T4 35。
accdoer上 rank 44，T1 100，T2 0，T3 5，T4 35。
难度难评，T1签，剩下的不可做？死磕T3了，猜一个结论假一个，打完暴力遗憾离场。
好像两个题库都挂了几分，不管了，赛前挂分RP就++。
慢报：5k_sync_closer成功地取得了NFLS模拟赛第一名的好成绩。
冒泡排序
签，就是将所有\(i\mod j=0\quad(j\in [1,k])\)的排序，然后输出，考察会不会用vector和sort。
但因为我人傻常数大，用的vector.erase(vector.begin())，加上学校机子太快了，然后被卡成了90。
点此查看代码
染色
可能是简单题吧，但我没看。
\(f_{i,j}\)表示以\(j\)结尾，长度为\(i\)的方案数，那么有\(f_{i,j}=\sum\limits_{k\ne j}f_{i-1,k}+1\)。
然后就用bitset优化即可。
最后的答案为\(\sum\limits_{i=1}^n\mathrm{C}_{n-1}^{i-1}\sum_{k=1}^mf_{k,i}\)
组合数判断奇偶的trick：如果\(n&m==m\)，则\(\mathrm{C}_{n}^m\)为奇数。
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#define Infile(x) freopen(#x".in","r",stdin)
#define Outfile(x) freopen(#x".out","w",stdout)
#define Ansfile(x) freopen(#x".ans","w",stdout)
#define Errfile(x) freopen(#x".err","w",stderr)
#ifdef LOCAL
FILE *InFile = Infile(in),*OutFile = Outfile(out);
// FILE *ErrFile = Errfile(err);
#else
FILE *InFile = Infile(color),*OutFile = Outfile(color);
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 1e5 + 1,M = 2e4 + 1;
int n,m,a[N];
bitset<N> f[M],tot,lst;
inline bool C(int n,int m){return ((n&m)==m);}
inline void solve(){
cin>>n>>m;
bool ans = 0;
rep(i,1,n,1) cin>>a[i];
rep(i,1,m,1) f[i].reset();
tot.reset();
rep(i,1,n,1){
int now = a[i];
lst = tot^f[now];
f[now] = lst<<1;
f[now].set(1);
tot = lst ^ f[now];
}
rep(i,1,n,1) ans ^= C(n-1,i-1)*tot[i];
cout<<ans;
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
int T;cin>>T;while(T--) solve();
}
图
挂一个20+KB的std和题解。
点此查看代码
#include <cstdio>
#include <map>
#include <iostream>
#include <algorithm>
#include <bitset>
#include <queue>
#include <stack>
#include <vector>
#include <random>
#include <cstring>
#include <ctime>
#include <cmath>
#include <assert.h>
#include <unordered_map>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define LL long long
#define pp pair<LL, LL>
#define mp make_pair
#define ull unsigned long long
namespace IO {
const int sz = 1 << 22;
char a[sz + 5], b[sz + 5], *p1 = a, *p2 = a, *t = b, p[105];
inline char gc() {
// return p1==p2?(p2=(p1=a)+fread(a,1,sz,stdin),p1==p2?EOF:*p1++):*p1++;
return getchar();
}
template <class T>
void gi(T& x) {
x = 0;
int f = 1;
char c = gc();
if (c == '-')
f = -1;
for (; c < '0' || c > '9'; c = gc())
if (c == '-')
f = -1;
for (; c >= '0' && c <= '9'; c = gc()) x = x * 10 + (c - '0');
x = x * f;
}
inline void flush() { fwrite(b, 1, t - b, stdout), t = b; }
inline void pc(char x) {
*t++ = x;
if (t - b == sz)
flush();
}
template <class T>
void pi(T x, char c = '\n') {
if (x < 0)
pc('-'), x = -x;
if (x == 0)
pc('0');
int t = 0;
for (; x; x /= 10) p[++t] = x % 10 + '0';
for (; t; --t) pc(p[t]);
pc(c);
}
struct F {
~F() { flush(); }
} f;
} // namespace IO
using IO::gi;
using IO::pc;
using IO::pi;
const int mod = 1e9 + 7;
inline int add(int x, int y) { return x + y >= mod ? x + y - mod : x + y; }
inline int dec(int x, int y) { return x - y < 0 ? x - y + mod : x - y; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
inline int qkpow(int a, int b) {
if (b < 0)
return 0;
int ans = 1, base = a % mod;
while (b) {
if (b & 1)
ans = 1ll * ans * base % mod;
base = 1ll * base * base % mod;
b >>= 1;
}
return ans;
}
int fac[1000005], inv[1000005], Invn[600005];
inline int binom(int n, int m) {
if (n < m || m < 0)
return 0;
return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}
void init_C(int n) {
fac[0] = 1;
for (int i = 1; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
inv[0] = 1;
inv[n] = qkpow(fac[n], mod - 2);
for (int i = n - 1; i >= 1; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
Invn[0] = Invn[1] = 1;
for (int i = 1; i <= 200000; i++) Invn[i] = (LL)(mod - mod / i) * Invn[mod % i] % mod;
}
const LL INF = 1e18;
struct node3 {
pp mi1, mi2;
inline void init() { mi1 = mi2 = pp(INF, 0); }
} g1[100005], g2[100005], wg1[100005], wg2[100005];
inline void Add(node3& w1, pp w2) {
if (!w2.second)
return;
if (w1.mi1.second == w2.second)
w1.mi1.first = min(w1.mi1.first, w2.first);
else if (w1.mi2.second == w2.second) {
w1.mi2.first = min(w1.mi2.first, w2.first);
if (w1.mi1.first > w1.mi2.first)
swap(w1.mi1, w1.mi2);
} else {
if (w2.first < w1.mi1.first)
w1.mi2 = w1.mi1, w1.mi1 = w2;
else if (w2.first < w1.mi2.first)
w1.mi2 = w2;
}
}
int Log[100005];
struct ST_min {
node3 f[100005][21];
inline node3 query(int l, int r) {
node3 res;
res.init();
if (l > r)
return res;
int k = Log[r - l + 1];
res = f[r - (1 << k) + 1][k];
Add(res, f[l][k].mi1);
Add(res, f[l][k].mi2);
return res;
}
inline void init(int N) {
for (int j = 1; (1 << j) <= N; j++)
for (int i = 1; i + (1 << j) - 1 <= N; i++) {
f[i][j] = f[i + (1 << (j - 1))][j - 1];
Add(f[i][j], f[i][j - 1].mi1);
Add(f[i][j], f[i][j - 1].mi2);
}
}
} T1[2], T2[2];
int son1[100005], son2[100005], dep11[100005], dep22[100005], seg1[100005], seg2[100005], rev11[100005],
rev22[100005];
int top1[100005], top2[100005];
int n, fa[200005], id1[100005], id2[100005], cnt1, cnt2, dfn1[100005], dfn2[100005];
int rev1[100005], rev2[100005], f2[100005][21], sz1[100005], sz2[100005], f1[100005][21];
int st1[100005][21], st2[100005][21];
LL jp1[100005][21], jp2[100005][21];
LL dep1[100005], dep2[100005];
pp mn[200005];
struct node {
int to, w;
};
vector<node> G1[100005], G2[100005];
inline int findSet(int u) { return fa[u] == u ? u : fa[u] = findSet(fa[u]); }
inline int Min1(int u, int v) { return dfn1[u] < dfn1[v] ? u : v; }
inline int Min2(int u, int v) { return dfn2[u] < dfn2[v] ? u : v; }
inline int LCA1(int u, int v) {
if (u == v)
return u;
if ((u = dfn1[u]) > (v = dfn1[v]))
swap(u, v);
int k = Log[v - u++];
return Min1(f1[u][k], f1[v - (1 << k) + 1][k]);
}
inline int LCA2(int u, int v) {
if (u == v)
return u;
if ((u = dfn2[u]) > (v = dfn2[v]))
swap(u, v);
int k = Log[v - u++];
return Min2(f2[u][k], f2[v - (1 << k) + 1][k]);
}
inline LL getdis(int op, int u, int v) {
if (op == 1)
return dep1[u] + dep1[v] - 2 * dep1[LCA1(u, v)];
else
return dep2[u] + dep2[v] - 2 * dep2[LCA2(u, v)];
}
inline void dfs1(int u, int ff) {
dep11[u] = dep11[ff] + 1;
f1[dfn1[u] = ++cnt1][0] = ff;
rev1[cnt1] = u;
sz1[u] = 1;
for (int i = 1; i <= 20; i++)
st1[u][i] = st1[st1[u][i - 1]][i - 1], jp1[u][i] = jp1[u][i - 1] + jp1[st1[u][i - 1]][i - 1];
for (auto to : G1[u]) {
int v = to.to, w = to.w;
if (v == ff)
continue;
dep1[v] = dep1[u] + w;
st1[v][0] = u, jp1[v][0] = w;
dfs1(v, u);
sz1[u] += sz1[v];
if (sz1[v] > sz1[son1[u]])
son1[u] = v;
}
}
inline void dfs11(int u, int ff) {
if (son1[u]) {
seg1[son1[u]] = ++seg1[0];
top1[son1[u]] = top1[u];
rev11[seg1[0]] = son1[u];
dfs11(son1[u], u);
}
for (auto to : G1[u]) {
int v = to.to, w = to.w;
if (v == ff)
continue;
if (!top1[v]) {
seg1[v] = ++seg1[0];
top1[v] = v;
rev11[seg1[0]] = v;
dfs11(v, u);
}
}
}
inline void dfs2(int u, int ff) {
dep22[u] = dep22[ff] + 1;
f2[dfn2[u] = ++cnt2][0] = ff;
rev2[cnt2] = u;
sz2[u] = 1;
for (int i = 1; i <= 20; i++)
st2[u][i] = st2[st2[u][i - 1]][i - 1], jp2[u][i] = jp2[u][i - 1] + jp2[st2[u][i - 1]][i - 1];
for (auto to : G2[u]) {
int v = to.to, w = to.w;
if (v == ff)
continue;
dep2[v] = dep2[u] + w;
st2[v][0] = u, jp2[v][0] = w;
dfs2(v, u);
sz2[u] += sz2[v];
if (sz2[v] > sz2[son2[u]])
son2[u] = v;
}
}
inline void dfs22(int u, int ff) {
if (son2[u]) {
seg2[son2[u]] = ++seg2[0];
top2[son2[u]] = top2[u];
rev22[seg2[0]] = son2[u];
dfs22(son2[u], u);
}
for (auto to : G2[u]) {
int v = to.to, w = to.w;
if (v == ff)
continue;
if (!top2[v]) {
seg2[v] = ++seg2[0];
top2[v] = v;
rev22[seg2[0]] = v;
dfs22(v, u);
}
}
}
struct node2 {
pp u, v;
} t[400005], po1[100005], po2[100005];
LL tag[400005];
#define ls(u) u << 1
#define rs(u) u << 1 | 1
inline node2 merge(int op, node2 A, node2 B) {
node2 tmp;
LL res = -1;
LL d1 =
(A.u.first == A.v.first ? A.u.second : A.u.second + A.v.second) + getdis(op, A.u.first, A.v.first);
LL d2 =
(B.u.first == B.v.first ? B.u.second : B.u.second + B.v.second) + getdis(op, B.u.first, B.v.first);
LL d3 =
(A.u.first == B.v.first ? A.u.second : A.u.second + B.v.second) + getdis(op, A.u.first, B.v.first);
LL d4 =
(B.u.first == A.v.first ? B.u.second : B.u.second + A.v.second) + getdis(op, B.u.first, A.v.first);
LL d5 =
(A.u.first == B.u.first ? A.u.second : A.u.second + B.u.second) + getdis(op, A.u.first, B.u.first);
LL d6 =
(A.v.first == B.v.first ? A.v.second : A.v.second + B.v.second) + getdis(op, A.v.first, B.v.first);
res = max(d1, d2), res = max(res, max(d3, d4)), res = max(res, max(d5, d6));
if (d1 == res)
tmp = node2{ A.u, A.v };
if (d2 == res)
tmp = node2{ B.u, B.v };
if (d3 == res)
tmp = node2{ A.u, B.v };
if (d4 == res)
tmp = node2{ B.u, A.v };
if (d5 == res)
tmp = node2{ A.u, B.u };
if (d6 == res)
tmp = node2{ A.v, B.v };
return tmp;
}
inline void push_down(int u) {
if (tag[u]) {
tag[ls(u)] += tag[u];
tag[rs(u)] += tag[u];
t[ls(u)].u.second += tag[u];
t[ls(u)].v.second += tag[u];
t[rs(u)].u.second += tag[u];
t[rs(u)].v.second += tag[u];
tag[u] = 0;
}
}
inline void updata(int op, int p, int l, int r, int L, int R, int w) {
if (L > R)
return;
if (L <= l && r <= R) {
tag[p] += w;
t[p].u.second += w;
t[p].v.second += w;
return;
}
push_down(p);
int mid = (l + r) >> 1;
if (L <= mid)
updata(op, ls(p), l, mid, L, R, w);
if (mid + 1 <= R)
updata(op, rs(p), mid + 1, r, L, R, w);
t[p] = merge(op, t[ls(p)], t[rs(p)]);
}
inline void build(int op, int p, int l, int r) {
tag[p] = 0;
if (l == r) {
if (op == 2)
t[p].u = t[p].v = pp(rev1[l], dep1[rev1[l]]);
else
t[p].u = t[p].v = pp(rev2[l], dep2[rev2[l]]);
return;
}
int mid = (l + r) >> 1;
build(op, ls(p), l, mid);
build(op, rs(p), mid + 1, r);
t[p] = merge(op, t[ls(p)], t[rs(p)]);
}
inline void redfs1(int u, int ff) {
po1[u] = t[1];
for (auto to : G1[u]) {
int v = to.to, w = to.w;
if (v == ff)
continue;
updata(2, 1, 1, n, dfn1[v], dfn1[v] + sz1[v] - 1, -w);
updata(2, 1, 1, n, 1, dfn1[v] - 1, w);
updata(2, 1, 1, n, dfn1[v] + sz1[v], n, w);
redfs1(v, u);
updata(2, 1, 1, n, dfn1[v], dfn1[v] + sz1[v] - 1, w);
updata(2, 1, 1, n, 1, dfn1[v] - 1, -w);
updata(2, 1, 1, n, dfn1[v] + sz1[v], n, -w);
}
}
inline void redfs2(int u, int ff) {
po2[u] = t[1];
for (auto to : G2[u]) {
int v = to.to, w = to.w;
if (v == ff)
continue;
updata(1, 1, 1, n, dfn2[v], dfn2[v] + sz2[v] - 1, -w);
updata(1, 1, 1, n, 1, dfn2[v] - 1, w);
updata(1, 1, 1, n, dfn2[v] + sz2[v], n, w);
redfs2(v, u);
updata(1, 1, 1, n, dfn2[v], dfn2[v] + sz2[v] - 1, w);
updata(1, 1, 1, n, 1, dfn2[v] - 1, -w);
updata(1, 1, 1, n, dfn2[v] + sz2[v], n, -w);
}
}
inline void dfss1(int u, int ff) {
g1[u].init();
wg1[u].init();
Add(g1[u], pp(0, id1[u]));
for (auto to : G1[u]) {
int v = to.to, w = to.w;
if (v == ff)
continue;
dfss1(v, u);
Add(g1[u], pp(g1[v].mi1.first + w, g1[v].mi1.second));
Add(g1[u], pp(g1[v].mi2.first + w, g1[v].mi2.second));
}
}
inline void redfss1(int u, int ff) {
node3 pre;
pre.init();
Add(wg1[u], pp(0, id1[u]));
for (auto to : G1[u]) {
int v = to.to, w = to.w;
if (v == ff)
continue;
Add(wg1[v], pp(wg1[u].mi1.first + w, wg1[u].mi1.second));
Add(wg1[v], pp(wg1[u].mi2.first + w, wg1[u].mi2.second));
Add(wg1[v], pp(pre.mi1.first + w, pre.mi1.second));
Add(wg1[v], pp(pre.mi2.first + w, pre.mi2.second));
Add(pre, pp(g1[v].mi1.first + w, g1[v].mi1.second));
Add(pre, pp(g1[v].mi2.first + w, g1[v].mi2.second));
}
reverse(G1[u].begin(), G1[u].end());
pre.init();
for (auto to : G1[u]) {
int v = to.to, w = to.w;
if (v == ff)
continue;
Add(wg1[v], pp(pre.mi1.first + w, pre.mi1.second));
Add(wg1[v], pp(pre.mi2.first + w, pre.mi2.second));
Add(pre, pp(g1[v].mi1.first + w, g1[v].mi1.second));
Add(pre, pp(g1[v].mi2.first + w, g1[v].mi2.second));
}
reverse(G1[u].begin(), G1[u].end());
for (auto to : G1[u]) {
int v = to.to, w = to.w;
if (v == ff)
continue;
redfss1(v, u);
}
}
inline void dfss2(int u, int ff) {
g2[u].init();
wg2[u].init();
Add(g2[u], pp(0, id2[u]));
for (auto to : G2[u]) {
int v = to.to, w = to.w;
if (v == ff)
continue;
dfss2(v, u);
Add(g2[u], pp(g2[v].mi1.first + w, g2[v].mi1.second));
Add(g2[u], pp(g2[v].mi2.first + w, g2[v].mi2.second));
}
}
inline void redfss2(int u, int ff) {
node3 pre;
pre.init();
Add(wg2[u], pp(0, id2[u]));
for (auto to : G2[u]) {
int v = to.to, w = to.w;
if (v == ff)
continue;
Add(wg2[v], pp(wg2[u].mi1.first + w, wg2[u].mi1.second));
Add(wg2[v], pp(wg2[u].mi2.first + w, wg2[u].mi2.second));
Add(wg2[v], pp(pre.mi1.first + w, pre.mi1.second));
Add(wg2[v], pp(pre.mi2.first + w, pre.mi2.second));
Add(pre, pp(g2[v].mi1.first + w, g2[v].mi1.second));
Add(pre, pp(g2[v].mi2.first + w, g2[v].mi2.second));
}
reverse(G2[u].begin(), G2[u].end());
pre.init();
for (auto to : G2[u]) {
int v = to.to, w = to.w;
if (v == ff)
continue;
Add(wg2[v], pp(pre.mi1.first + w, pre.mi1.second));
Add(wg2[v], pp(pre.mi2.first + w, pre.mi2.second));
Add(pre, pp(g2[v].mi1.first + w, g2[v].mi1.second));
Add(pre, pp(g2[v].mi2.first + w, g2[v].mi2.second));
}
reverse(G2[u].begin(), G2[u].end());
for (auto to : G2[u]) {
int v = to.to, w = to.w;
if (v == ff)
continue;
redfss2(v, u);
}
}
inline node3 query22(int op, int u, int v, LL ex) {
int fu = top2[u], fv = top2[v];
node3 res;
res.init();
while (fu != fv) {
if (dep22[fu] >= dep22[fv]) {
node3 tmp = T2[op].query(seg2[fu], seg2[u]);
Add(res, tmp.mi1), Add(res, tmp.mi2);
u = st2[fu][0];
} else {
node3 tmp = T2[op].query(seg2[fv], seg2[v]);
Add(res, tmp.mi1), Add(res, tmp.mi2);
v = st2[fv][0];
}
fu = top2[u], fv = top2[v];
}
if (dep22[u] > dep22[v])
swap(u, v);
node3 tmp = T2[op].query(seg2[u], seg2[v]);
Add(res, tmp.mi1), Add(res, tmp.mi2);
return node3{ pp(res.mi1.first + ex, res.mi1.second), pp(res.mi2.first + ex, res.mi2.second) };
}
inline pp query2(int u, int v, LL w1, LL w2, int c) { //��ɫ������ c
int lca = LCA2(u, v);
// if(lca!=1)cerr<<lca<<" "<<"FUCK"<<endl;
int to = u;
LL sum = w1, tot = getdis(2, u, v) + w1 + w2;
node3 res, tmp;
res.init();
LL ex = max(getdis(2, u, lca) + w1, getdis(2, v, lca) + w2);
Add(res, pp(wg2[lca].mi1.first + ex, wg2[lca].mi1.second));
Add(res, pp(wg2[lca].mi2.first + ex, wg2[lca].mi2.second));
if (w1 >= tot - w1) {
node3 tmp;
tmp = query22(1, u, lca, w1 + dep2[u]);
Add(res, tmp.mi1), Add(res, tmp.mi2);
} else {
for (int i = 20; i >= 0; i--) {
if (sum + jp2[to][i] <= tot - sum - jp2[to][i]) {
sum += jp2[to][i];
to = st2[to][i];
}
}
node3 tmp;
if (dep22[to] <= dep22[lca]) { //ȫ���� v ��
tmp = query22(0, u, lca, w2 + dep2[v] - 2 * dep2[lca]);
Add(res, tmp.mi1), Add(res, tmp.mi2);
} else {
tmp = query22(0, u, to, w2 + dep2[v] - 2 * dep2[lca]);
Add(res, tmp.mi1), Add(res, tmp.mi2);
tmp = query22(1, st2[to][0], lca, w1 + dep2[u]);
Add(res, tmp.mi1), Add(res, tmp.mi2);
}
}
to = v;
sum = w2;
if (w2 >= tot - w2) {
tmp = query22(1, v, lca, w2 + dep2[v]);
Add(res, tmp.mi1), Add(res, tmp.mi2);
} else {
for (int i = 20; i >= 0; i--) {
if (sum + jp2[to][i] <= tot - sum - jp2[to][i]) {
sum += jp2[to][i];
to = st2[to][i];
}
}
if (dep22[to] <= dep22[lca]) { //ȫ���� u ��
tmp = query22(0, v, lca, w1 + dep2[u] - 2 * dep2[lca]);
Add(res, tmp.mi1), Add(res, tmp.mi2);
} else {
tmp = query22(0, v, to, w1 + dep2[u] - 2 * dep2[lca]);
Add(res, tmp.mi1), Add(res, tmp.mi2);
tmp = query22(1, st2[to][0], lca, w2 + dep2[v]);
Add(res, tmp.mi1), Add(res, tmp.mi2);
}
}
if (res.mi1.second == c)
return res.mi2;
return res.mi1;
}
inline node3 query11(int op, int u, int v, LL ex) {
int fu = top1[u], fv = top1[v];
node3 res;
res.init();
while (fu != fv) {
if (dep11[fu] >= dep11[fv]) {
node3 tmp = T1[op].query(seg1[fu], seg1[u]);
Add(res, tmp.mi1), Add(res, tmp.mi2);
u = st1[fu][0];
} else {
node3 tmp = T1[op].query(seg1[fv], seg1[v]);
Add(res, tmp.mi1), Add(res, tmp.mi2);
v = st1[fv][0];
}
fu = top1[u], fv = top1[v];
}
if (dep11[u] > dep11[v])
swap(u, v);
node3 tmp = T1[op].query(seg1[u], seg1[v]);
Add(res, tmp.mi1), Add(res, tmp.mi2);
return node3{ pp(res.mi1.first + ex, res.mi1.second), pp(res.mi2.first + ex, res.mi2.second) };
}
inline pp query1(int u, int v, LL w1, LL w2, int c) { //��ɫ������ c
int lca = LCA1(u, v);
// if(lca!=1)cerr<<lca<<" "<<"FUCK"<<endl;
int to = u;
LL sum = w1, tot = getdis(1, u, v) + w1 + w2;
node3 res, tmp;
res.init();
LL ex = max(getdis(1, u, lca) + w1, getdis(1, v, lca) + w2);
Add(res, pp(wg1[lca].mi1.first + ex, wg1[lca].mi1.second));
Add(res, pp(wg1[lca].mi2.first + ex, wg1[lca].mi2.second));
if (w1 >= tot - w1) {
tmp = query11(1, u, lca, w1 + dep1[u]);
Add(res, tmp.mi1), Add(res, tmp.mi2);
} else {
for (int i = 20; i >= 0; i--) {
if (sum + jp1[to][i] <= tot - sum - jp1[to][i]) {
sum += jp1[to][i];
to = st1[to][i];
}
}
node3 tmp;
if (dep11[to] <= dep11[lca]) { //ȫ���� v ��
tmp = query11(0, u, lca, w2 + dep1[v] - 2 * dep1[lca]);
Add(res, tmp.mi1), Add(res, tmp.mi2);
} else {
tmp = query11(0, u, to, w2 + dep1[v] - 2 * dep1[lca]);
Add(res, tmp.mi1), Add(res, tmp.mi2);
tmp = query11(1, st1[to][0], lca, w1 + dep1[u]);
Add(res, tmp.mi1), Add(res, tmp.mi2);
}
}
to = v;
sum = w2;
if (w2 >= tot - w2) {
node3 tmp;
tmp = query11(1, v, lca, w2 + dep1[v]);
Add(res, tmp.mi1), Add(res, tmp.mi2);
} else {
for (int i = 20; i >= 0; i--) {
if (sum + jp1[to][i] <= tot - sum - jp1[to][i]) {
sum += jp1[to][i];
to = st1[to][i];
}
}
if (dep11[to] <= dep11[lca]) { //ȫ���� u ��
tmp = query11(0, v, lca, w1 + dep1[u] - 2 * dep1[lca]);
Add(res, tmp.mi1), Add(res, tmp.mi2);
} else {
tmp = query11(0, v, to, w1 + dep1[u] - 2 * dep1[lca]);
Add(res, tmp.mi1), Add(res, tmp.mi2);
tmp = query11(1, st1[to][0], lca, w2 + dep1[v]);
Add(res, tmp.mi1), Add(res, tmp.mi2);
}
}
if (res.mi1.second == c)
return res.mi2;
return res.mi1;
}
inline void solve() {
for (int i = 2; i <= 100000; i++) Log[i] = Log[i >> 1] + 1;
gi(n);
for (int i = 1; i < n; i++) {
int u, v, w;
gi(u), gi(v), gi(w);
G1[u].push_back(node{ v, w });
G1[v].push_back(node{ u, w });
}
for (int i = 1; i < n; i++) {
int u, v, w;
gi(u), gi(v), gi(w);
G2[u].push_back(node{ v, w });
G2[v].push_back(node{ u, w });
}
seg1[0] = seg1[1] = top1[1] = rev11[1] = 1;
seg2[0] = seg2[1] = top2[1] = rev22[1] = 1;
dfs1(1, 0), dfs2(1, 0), dfs11(1, 0), dfs22(1, 0);
for (int j = 1; (1 << j) <= cnt1; j++)
for (int i = 1; i + (1 << j) - 1 <= cnt1; i++)
f1[i][j] = Min1(f1[i][j - 1], f1[i + (1 << (j - 1))][j - 1]);
for (int j = 1; (1 << j) <= cnt2; j++)
for (int i = 1; i + (1 << j) - 1 <= cnt2; i++)
f2[i][j] = Min2(f2[i][j - 1], f2[i + (1 << (j - 1))][j - 1]);
build(2, 1, 1, n);
redfs1(1, 0);
build(1, 1, 1, n);
redfs2(1, 0);
for (int i = 1; i <= 2 * n; i++) fa[i] = i;
int cnt = 2 * n;
LL ans = 0;
while (cnt > 1) {
for (int i = 1; i <= n; i++) id1[i] = findSet(i), mn[i] = pp(INF, 0);
for (int i = 1; i <= n; i++) id2[i] = findSet(i + n), mn[i + n] = pp(INF, 0);
dfss1(1, 0), dfss2(1, 0);
redfss1(1, 0), redfss2(1, 0);
for (int i = 1; i <= n; i++) {
int u = rev11[i], v = rev22[i];
T1[0].f[i][0].mi1 = pp(g1[u].mi1.first + dep1[u], g1[u].mi1.second);
T1[0].f[i][0].mi2 = pp(g1[u].mi2.first + dep1[u], g1[u].mi2.second);
T1[1].f[i][0].mi1 = pp(g1[u].mi1.first - dep1[u], g1[u].mi1.second);
T1[1].f[i][0].mi2 = pp(g1[u].mi2.first - dep1[u], g1[u].mi2.second);
T2[0].f[i][0].mi1 = pp(g2[v].mi1.first + dep2[v], g2[v].mi1.second);
T2[0].f[i][0].mi2 = pp(g2[v].mi2.first + dep2[v], g2[v].mi2.second);
T2[1].f[i][0].mi1 = pp(g2[v].mi1.first - dep2[v], g2[v].mi1.second);
T2[1].f[i][0].mi2 = pp(g2[v].mi2.first - dep2[v], g2[v].mi2.second);
}
T1[0].init(n), T2[0].init(n), T1[1].init(n), T2[1].init(n);
for (int i = 1; i <= n; i++) {
int u = po1[i].u.first, v = po1[i].v.first;
LL w1 = po1[i].u.second, w2 = po1[i].v.second;
mn[id1[i]] = min(mn[id1[i]], query2(u, v, w1, w2, id1[i]));
}
for (int i = 1; i <= n; i++) {
int u = po2[i].u.first, v = po2[i].v.first;
LL w1 = po2[i].u.second, w2 = po2[i].v.second;
mn[id2[i]] = min(mn[id2[i]], query1(u, v, w1, w2, id2[i]));
}
for (int i = 1; i <= 2 * n; i++) {
if (mn[i].second) {
int u = i, v = mn[i].second;
u = findSet(u), v = findSet(v);
if (u != v) {
fa[v] = u;
ans += mn[i].first;
cnt--;
}
}
}
// cerr<<cnt<<endl;
}
pi(ans);
}
/*
Ҫһ������
*/
signed main() {
freopen("graph.in", "r", stdin);
freopen("graph.out", "w", stdout);
srand(time(0));
solve();
return 0;
}
/*
*/
山峦
打的搜索＋剪枝，喜提35，不想调了。
