又双叒叕垫底了。
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 LOCALFILE *InFile = Infile(in),*OutFile = Outfile(out);// FILE *ErrFile = Errfile(err);
#elseFILE *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)];elsereturn 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]]);elset[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) { //��ɫ������ cint 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) { //��ɫ������ cint 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，不想调了。
