## 【模板库】线段树合并

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200009;
const int M = N * 21;

int n, m, vis[N], head[N], nxt[N], to[N];
int dep[N], beg[N], out[N], sz[N], fa[N];
struct Data{
int t, x, y;
inline Data() {
}
inline Data(bool a, int b, int c):t(a), x(b), y(c) {
}
}opt[N];

char c = getchar(); int ret = 0, f = 1;
for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
return ret * f;
}

inline void AddEdge(int u, int v) {
static int E = 1;
}

inline void DFS(int w, int f) {
static int D = 0;
vis[w] = 1;
beg[w] = ++D;
dep[w] = dep[f] + 1;
for (int i = head[w]; i; i = nxt[i]) {
if (to[i] != f) {
DFS(to[i], w);
}
}
out[w] = D;
}

inline int find(int x) {
return fa[x] == x? x: fa[x] = find(fa[x]);
}

class SegmentTree{
int cnt, ch[M][2], sum[M], root[N];
public:
inline void insert(int p, int v) {
insert(root[p], 1, n, v);
}
inline void merge(int a, int b) {
root[a] = Merge(root[a], root[b]);
}
inline int query(int p, int l, int r) {
return query(root[p], 1, n, l, r);
}
private:
inline int Merge(int a, int b) {
if (!a || !b) {
return a + b;
} else {
sum[a] += sum[b];
ch[a][0] = Merge(ch[a][0], ch[b][0]);
ch[a][1] = Merge(ch[a][1], ch[b][1]);
return a;
}
}
inline void insert(int &w, int l, int r, int p) {
sum[w = ++cnt] = 1;
if (l < r) {
int mid = l + r + 1 >> 1;
if (p < mid) {
insert(ch[w][0], l, mid - 1, p);
} else {
insert(ch[w][1], mid, r, p);
}
}
}
inline int query(int w, int l, int r, int L, int R) {
if (!w) {
return 0;
} else if (L <= l && r <= R) {
return sum[w];
} else {
int mid = l + r + 1 >> 1, ret = 0;
ret += L < mid? query(ch[w][0], l, mid - 1, L, R): 0;
ret += mid <= R? query(ch[w][1], mid, r, L, R): 0;
return ret;
}
}
}SGT;

int main() {
for (int i = 1; i <= m; i++) {
char cmd[3];
scanf("%s", cmd);
if (cmd[0] == 'A') {
}
opt[i] = Data(cmd[0] == 'A', u, v);
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
DFS(i, i);
}
}
for (int i = 1; i <= n; i++) {
sz[i] = 1;
fa[i] = i;
SGT.insert(i, beg[i]);
}
for (int i = 1; i <= m; i++) {
int u = opt[i].x, v = opt[i].y;
if (opt[i].t == 1) {
SGT.merge(find(u), find(v));
sz[find(u)] += sz[find(v)];
fa[find(v)] = find(u);
} else {
if (dep[u] < dep[v]) {
swap(u, v);
}
int p1 = SGT.query(find(u), beg[u], out[u]);
int p2 = sz[find(u)] - p1;
printf("%lld\n", (LL)p1 * p2);
}
}
return 0;
}

## 【模板库】拉格朗日插值法

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200;
const int MOD = 1000000007;

int n,m,K,r[N],u[N],f[N],g[N],h[N],alpha[N],C[N][N];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline int Pow(int w, int t) {
int ret = 1;
for (;t;t>>=1,w=(LL)w*w%MOD) {
if (t & 1) {
ret = (LL)ret * w % MOD;
}
}
return ret;
}

inline int LagrangePolynomial(int x, int len, int *ff, int *xx) {
int ret = 0;
for (int i=1;i<=len;i++) {
int tmp = ff[i];
for (int j=1;j<=len;j++) {
if (i == j) continue;
tmp = (LL)tmp * (x - xx[j]) % MOD;
tmp = (LL)tmp * Pow(xx[i] - xx[j], MOD-2) % MOD;
}
ret = (ret + tmp) % MOD;
}
return (ret + MOD) % MOD;
}

int main() {
for (int i=1;i<=m;i++) {
}
for (int i=1;i<=m;i++) {
}
//预处理组合数
C[0][0] = 1;
for (int i=1;i<=n;i++) {
C[i][0] = 1;
for (int j=1;j<=i;j++) {
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
}
}
//拉格朗日插值
for (int w=1;w<=m;w++) {
for (int i=1;i<=n+1;i++) {
f[i] = 0; h[i] = i;
for (int j=1;j<=i;j++) {
f[i] = (f[i] + (LL)Pow(i-j, r[w]-1) * Pow(j, n-r[w])) % MOD;
}
}
g[w] = LagrangePolynomial(u[w], n+1, f, h);
}
//广义容斥原理
int ans = 0;
for (int i=K,t=1;i<=n;i++,t*=-1) {
alpha[i] = C[n-1][i];
for (int j=1;j<=m;j++) {
alpha[i] = (LL)alpha[i] * C[n-1-i][r[j]-1] % MOD * g[j] % MOD;
}
ans = (ans + t * (LL)C[i][K] * alpha[i]) % MOD;
}
printf("%d\n",(ans+MOD)%MOD);
return 0;
}

## 【模板库】半平面交

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 10000;
const double EPS = 1e-8;

int n,m;

struct Point{
double x,y;
inline Point() {}
inline Point(double a, double b):x(a),y(b) {}
inline Point operator + (const Point &P) const {return Point(x+P.x, y+P.y);}
inline Point operator - (const Point &P) const {return Point(x-P.x, y-P.y);}
inline Point operator * (double d) const {return Point(x*d, y*d);}
inline Point operator / (double d) const {return Point(x/d, y/d);}
inline double operator * (const Point &P) const {return x*P.x + y*P.y;}
inline double operator ^ (const Point &P) const {return x*P.y - P.x*y;}
}p[N],cvx[N];

struct Line{
Point a,b; double slp;
inline Line() {}
inline Line(const Point &x, const Point &y) {a = x; b = y; slp = atan2(b.y-a.y, b.x-a.x);}
inline bool operator < (const Line &L) const {return slp < L.slp - EPS || (fabs(slp-L.slp) < EPS && ((b-a)^(L.b-a)) < -EPS);}
inline bool operator != (const Line &L) {return fabs(slp - L.slp) > EPS;}
inline bool onleft(const Point &P) {return ((b - a) ^ (P - a)) > EPS;}
inline double len() {return sqrt((b - a) * (b - a));}
inline Point ins(const Line &L) {
double s1 = (b - L.b) ^ (L.a - L.b);
double s2 = (a - L.a) ^ (L.b - L.a);
Point tmp = a + (((b - a) * s2) / (s1 + s2));
return a + (((b - a) * s2) / (s1 + s2));
}
}l[N],que[N];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void HalfPlaneIntersection(int tot, Line *a, int &cnt, Line *b, Point *c) {
sort(a+1, a+1+tot); cnt = tot; tot = 1;
for (int i=2;i<=cnt;i++) if (a[i] != a[i-1]) a[++tot] = a[i];
b[1] = a[1]; b[2] = a[2]; int l=1,r=2;
for (int i=3;i<=tot;i++) {
while (l < r && !a[i].onleft(b[r-1].ins(b[r]))) r--;
while (l < r && !a[i].onleft(b[l].ins(b[l+1]))) l++;
b[++r] = a[i];
}
while (l < r && !b[l].onleft(b[r].ins(b[r-1]))) r--;
while (l < r && !b[r].onleft(b[l].ins(b[l+1]))) l++;
cnt = 0; b[0] = b[r];
for (int i=l;i<=r;i++) b[++cnt] = b[i];
for (int i=1;i<=cnt;i++) c[i] = b[i].ins(b[i-1]);
}

int main() {
for (int i=1;i<=n;i++) {
p[m+1] = p[1];
for (int j=1;j<=m;j++) l[++tot] = Line(p[j], p[j+1]);
}
HalfPlaneIntersection(tot, l, cnt, que, cvx);
double vout = 0;
for (int i=2;i<cnt;i++) vout += (cvx[i] - cvx[1]) ^ (cvx[i+1] - cvx[1]);
printf("%.3lf\n",vout/2);
return 0;
}

## 【模板库】二维凸包

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define LL long long
using namespace std;

const int N = 100000;
const double EPS = 1e-8;

int n,cnt;

struct Point{
double x,y;
inline Point() {}
inline Point(double a, double b):x(a),y(b) {}
inline Point operator + (const Point &A) {return Point(x+A.x, y+A.y);}
inline Point operator - (const Point &A) {return Point(x-A.x, y-A.y);}
inline Point operator / (double A) {return Point(x/A, y/A);}
inline Point operator * (double A) {return Point(x*A, y*A);}
inline double operator * (const Point &A) {return x*A.x + y*A.y;}
inline double operator ^ (const Point &A) {return x*A.y - A.x*y;}
inline bool operator < (const Point &B) const {return x < B.x - EPS || (fabs(x-B.x) < EPS && y < B.y - EPS);}
inline bool operator == (const Point &B) const {return fabs(x - B.x) + fabs(y - B.y) < EPS;}
}p[N],cvx[N];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void ConvexHull(int tot, Point *a, int &sz, Point *ret) {
if (!tot) {sz = 0; return;}
sort(a+1, a+1+tot); ret[sz=1] = a[1];
tot = unique(a+1, a+1+tot) - a - 1;
for (int i=2;i<=tot;i++) {
while (sz > 1 && ((ret[sz] - ret[sz-1]) ^ (a[i] - ret[sz])) < EPS) sz--;
ret[++sz] = a[i];
}
for (int i=tot-1,mn=sz;i>0;i--) {
while (sz > mn && ((ret[sz] - ret[sz-1]) ^ (a[i] - ret[sz])) < EPS) sz--;
ret[++sz] = a[i];
}
sz -= sz > 2;
}

int main() {
ConvexHull(n, p, cnt, cvx);
double vout = 0;
for (int i=2;i<cnt;i++)
vout += (cvx[i] - cvx[1]) ^ (cvx[i+1] - cvx[1]) / 2;
printf("%d\n",(int)(vout/50));
return 0;
}

## 【模板库】FWT

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int MOD = 1000000007;
const int REV = 500000004;

bool vis[N];
int arr[N];

char c = getchar(); int ret = 0, f = 1;
for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
return ret * f;
}

inline int Pow(int w, int t) {
int ret = 1;
for (; t; t >>= 1, w = (LL)w * w % MOD) {
if (t & 1) {
ret = (LL)ret * w % MOD;
}
}
return ret;
}

inline void FWT(int *a, int len, int opt = 1) {
for (int d = 1; d < len; d <<= 1) {
for (int i = 0; i < len; i += d << 1) {
for (int j = 0; j < d; j++) {
int t1 = a[i + j], t2 = a[i + j + d];
//XOR
if (opt == 1) {
a[i + j] = (t1 + t2) % MOD;
a[i + j + d] = (t1 - t2) % MOD;
} else {
a[i + j] = (LL)(t1 + t2) * REV % MOD;
a[i + j + d] = (LL)(t1 - t2) * REV % MOD;
}
/*
AND
if (opt == 1) {
arr[i + j] = t1 + t2;
//arr[i + j + d] = t2;
} else {
arr[i + j] = t1 - r2;
//arr[i + j + d] = t2;
}
*/
/*
OR
if (opt == 1) {
//arr[i + j] = t1;
arr[i + j + d] = t2 + t1;
} else {
//arr[i + j] = t1;
arr[i + j + d] = t2 - t1;
}
*/
}
}
}
}

int main() {
for (int n, m; ~scanf("%d %d", &n, &m); ) {
memset(arr, 0, sizeof(arr));
for (int i = 2; i <= m; i++) {
if (!vis[i]) {
arr[i] = 1;
for (int j = i << 1; 0 <= j && j <= m; j += i) {
vis[j] = 1;
}
}
}
int len = 1;
for (; len <= m; len <<= 1);
FWT(arr, len);
for (int i = 0; i < len; i++) {
arr[i] = Pow(arr[i], n);
}
FWT(arr, len, -1);
printf("%d\n", (arr[0] + MOD) % MOD);
}
return 0;
}

## 【模板库】Splay

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int INF = 0x7fffffff;
const int N = 200009;

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

class Splay{
struct Node{int ch[2],val,mn,sz,fa,delta,rev;}p[N]; int cnt;
public:
inline Splay() { //init the splay and place begining(1) and ending(2) of the sequence
cnt = 2; p[1].ch[1] = 2;
p[1].val = p[1].mn = INF;
p[2].val = p[2].mn = INF;
p[1].sz = 2; p[2].sz = 1;
p[1].fa = p[2].fa = 1;
}
inline void insert(int pos, int v) { ++pos; //insert a new node with value v as ths (pos + 1) node
int w; splay(w=rank(1, pos), 1);
int nw; splay(nw=rank(1, pos+1), w);
p[nw].ch[0] = ++cnt; p[cnt].fa = nw;
p[cnt].mn = p[cnt].val = v; p[cnt].sz = 1;
maintain(nw); maintain(w); maintain(1);
}
inline void add(int l, int r, int v) { ++l; ++r; //add value v to elements of range[l,r]
int w; splay(w=rank(1, l-1), 1);
int nw; splay(nw=rank(1, r+1), w);
p[p[nw].ch[0]].delta += v;
PushDown(p[nw].ch[0]); maintain(nw);
maintain(w); maintain(1);
}
inline int query(int l, int r) { ++l; ++r; //query the min element in range[l,r]
int w; splay(w=rank(1, l-1), 1);
int nw; splay(nw=rank(1, r+1), w);
return PushDown(p[nw].ch[0]), p[p[nw].ch[0]].mn;
}
inline void remove(int r) { ++r; //remove the r node
int w; splay(w=rank(1, r-1), 1);
int nw; splay(nw=rank(1, r+1), w);
p[nw].ch[0] = 0; maintain(nw);
maintain(w); maintain(1);
}
inline void reverse(int l, int r) { ++l; ++r; //reverse the elements in range[l,r]
int w; splay(w=rank(1, l-1), 1);
int nw; splay(nw=rank(1, r+1), w);
p[p[nw].ch[0]].rev ^= 1;
}
inline void Rotate(int l, int r, int t) { //rotate the elements in range[l,r] t steps
if (l==r||!(t%=((++r) - (++l) + 1))) return;
int w; splay(w=rank(1, l-1), 1);
int nw; splay(nw=rank(1, r+1), w);
int nnw; splay(nnw=rank(p[nw].ch[0], r-l-t+1), nw);
int nnnw; splay(nnnw=rank(p[nnw].ch[1], t), nnw);
p[nw].ch[0] = nnnw; p[nnnw].ch[1] = nnw; p[nnw].ch[1] = 0;
p[nnw].fa = nnnw; p[nnnw].fa = nw;
maintain(nnw); maintain(nnnw);
}
private:
inline void PushDown(int w) {
if (p[w].delta) {
p[w].mn += p[w].delta; p[w].val += p[w].delta;
p[p[w].ch[1]].delta += p[w].delta;
p[p[w].ch[0]].delta += p[w].delta;
p[w].delta = 0;
}
if (p[w].rev) {
swap(p[w].ch[0], p[w].ch[1]); p[w].rev = 0;
p[p[w].ch[0]].rev ^= 1; p[p[w].ch[1]].rev ^= 1;
}
}
inline void maintain(int w) {
p[w].mn = p[w].val; p[w].sz = p[p[w].ch[0]].sz + p[p[w].ch[1]].sz + 1;
if (p[w].ch[0]) PushDown(p[w].ch[0]), p[w].mn = min(p[w].mn, p[p[w].ch[0]].mn);
if (p[w].ch[1]) PushDown(p[w].ch[1]), p[w].mn = min(p[w].mn, p[p[w].ch[1]].mn);
}
inline void rotate(int w) { //rotate w to its father
int f=p[w].fa,t=p[f].ch[1]==w,ff=p[f].fa;
p[f].ch[t] = p[w].ch[t^1]; p[p[w].ch[t^1]].fa = f;
p[w].ch[t^1] = f; p[w].fa = p[f].fa; p[f].fa = w;
if (ff != f) p[ff].ch[p[ff].ch[1]==f] = w;
maintain(f); maintain(w);
}
inline void splay(int w, int pur) { //splay w to pur's son
if (w == pur) return;
for (int f,ff;f=p[w].fa,p[w].fa!=pur;) {
((ff=p[f].fa) == pur)? rotate(w):
(((p[f].ch[1]==w)^(p[ff].ch[1]==f))?rotate(w),rotate(f):rotate(f),rotate(w));
}
}
int rank(int w, int t) { //function rank is needed to be called before each splay operation to push down tags
PushDown(w); if (t<=0) return w; int szt = p[p[w].ch[0]].sz;
if (szt >= t) return rank(p[w].ch[0], t);
else if (szt + 1 == t) return w;
else return rank(p[w].ch[1], t-1-szt);
}
}SP;

int main() {
int n = read(); char opt[10];
scanf("%s",opt+1);
if (opt[1] == 'A') {
} else if (opt[1] == 'R' && opt[4] == 'E') {
SP.reverse(l, r);
} else if (opt[1] == 'R') {
} else if (opt[1] == 'I') {
SP.insert(l, r);
} else if (opt[1] == 'D') {
} else {
printf("%d\n",SP.query(l,r));
}
}
return 0;
}

## 【模板库】原根

#include<bits/stdc++.h>
#define LL long long
using namespace std;

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline int Get_Primitive_Root(int w) {
vector<int> pri;
for (int i=2,lim=ceil(sqrt(w)),cur=w-1;i<lim;i++) {
if (cur % i == 0) {
pri.push_back(i);
while (cur % i == 0)
cur /= i;
}
if (cur > 1 && i == lim - 1)
pri.push_back(cur);
}
static auto Pow = [](int w, int t, int MOD) {
int ret = 1;
for (;t;t>>=1,w=(LL)w*w%MOD)
if (t & 1) ret = (LL)ret * w % MOD;
return ret;
};
if (!pri.size()) return 2;
for (int i=2;i<=w;i++) {
for (int j=pri.size()-1;~j;j--) {
if (Pow(i,w/pri[j],w) == 1) break;
if (!j) return i;
}
}
}

int main() {
return 0;
}

## 【模板库】一般图最大匹配

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 501;
const int MOD = 998244353;

int n,m;

class Maximum_Matchings_in_General_Graph{
int a[N][N],b[N][N],G[N][N];
int tot,pat[N],id[N],num[N];
bool del_x[N],del_y[N];
public:
inline void Add_Edge(int u, int v) {
G[u][v] = a[u][v] = rand() % (MOD - 1) + 1;
G[v][u] = a[v][u] = -a[u][v];
}
inline int solve() {
for (int i=1;i<=n;i++) id[i] = i;
Gauss(n);
for (int i=1;i<=n;i++)
if (a[id[i]][id[i]])
num[++tot] = i;
for (int i=1;i<=tot;i++)
for (int j=1;j<=tot;j++)
a[i][j] = G[num[i]][num[j]];
Gauss(tot, 1);
for (int i=1;i<=tot;i++) {
if (!del_x[i]) {
for (int j=1;j<=tot;j++) {
if (!del_x[j] && G[num[i]][num[j]] && b[i][j]) {
pat[num[i]] = num[j];
pat[num[j]] = num[i];
Eliminat(i, j);
Eliminat(j, i);
break;
}
}
}
}
}
inline void print() {
printf("%d\n",tot>>1);
for (int i=1;i<=n;i++)
printf("%d ",pat[i]);
}
private:
inline int Pow(int w, int t) {
int ret = 1;
for (;t;t>>=1,w=(LL)w*w%MOD)
if (t & 1) ret = (LL)ret * w % MOD;
return ret;
}
inline void Gauss(int sz, bool I = 0) {
for (int i=1;i<=sz;++i) b[i][i] = 1;
for (int i=1;i<=sz;++i) {
for (int j=i;j<=sz;++j) {
if (a[j][i]) {
swap(id[i], id[j]);
swap(a[i], a[j]);
if (I) swap(b[i], b[j]);
break;
}
}
if (!a[i][i]) continue;
int inv = Pow(a[i][i], MOD - 2);
for (int j=1;j<=sz;++j) if (a[i][j]) a[i][j] = (LL)a[i][j] * inv % MOD;
if (I) for (int j=1;j<=sz;++j) if (b[i][j]) b[i][j] = (LL)b[i][j] * inv % MOD;
for (int j=1;j<=sz;++j) {
if (j != i && a[j][i]) {
LL tmp = a[j][i];
for (int k=1;k<=sz;++k) if (a[i][k]) a[j][k] = (a[j][k] - tmp * a[i][k]) % MOD;
if (I) for (int k=1;k<=sz;++k) if (b[i][k]) b[j][k] = (b[j][k] - tmp * b[i][k]) % MOD;
}
}
}
}
inline void Eliminat(int x, int y) {
del_x[x] = del_y[y] = 1;
LL inv = Pow(b[x][y], MOD - 2);
for (int i=1;i<=tot;++i) {
if (!del_y[i]) {
LL tmp = b[x][i] * inv % MOD;
for (int j=1;j<=tot;++j) {
if (!del_x[j] && b[y][j]) {
b[i][j] = (b[i][j] - tmp * b[y][j]) % MOD;
}
}
}
}
}
}MMGG;

static const int BUF_SIZE = 1000000;
static char buf[BUF_SIZE],*p1=0,*p2=0;
if (p1 == p2){
if (p2==p1) return -1;
} return *p1++;
}

return ret*f;
}

int main() {
srand(19260817);
for (int i=1,u,v;i<=m;i++) {
}
MMGG.solve();
MMGG.print();
return 0;
}

## 【模板库】树上点分治

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 40000 + 9;
const int M = N << 1;

int n,k,vout;

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void Add_Edge(int u, int v, int w) {
static int T = 0;
to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}

namespace Node_Decomposition{
#define ND Node_Decomposition
const int INF = 10000000;
int vis[N],dep[N],sum[N];
int tot,cur,num_node,root;

void Get_Root(int w, int f) {
int mx = 0; sum[w] = 1;
if (to[i] != f && !vis[to[i]]) {
Get_Root(to[i], w);
mx = max(mx, sum[to[i]]);
sum[w] += sum[to[i]];
}
}
mx = max(mx, num_node - mx);
if (mx < cur) root = w, cur = mx;
}

void Get_Dep(int w, int f, int bas) {
if (to[i] != f && !vis[to[i]]) {
dep[++tot] = bas + cost[i];
Get_Dep(to[i], w, dep[tot]);
}
}
}

inline int cal(int w, int bas) {
dep[tot=1] = bas;
Get_Dep(w, w, bas);
sort(dep+1, dep+1+tot);
int r = tot, l = 1, ret = 0;
while (l < r) {
while (l < r && dep[l] + dep[r] > k) r--;
ret += r - l++;
}
return ret;
}

void solve(int w, int sz) {
vis[w] = 1;
vout += cal(w, 0);
if (!vis[to[i]]) {
vout -= cal(to[i], cost[i]);
num_node = sum[to[i]] < sum[w] ? sum[to[i]] : sz - sum[w];
cur = INF; Get_Root(to[i], w);
solve(root, num_node);
}
}
}

void solve() {
num_node = n; cur = INF;
Get_Root(1, 1);
solve(root, n);
}
};

int main() {
for (int i=1,u,v,w;i<n;i++) {
}
ND::solve();
printf("%d",vout);
return 0;
}

## 【模板库】最强流读入

namespace fastIO{
#define BUF_SIZE 100000
#define OUT_SIZE 100000
#define ll long long
bool IOerror=0;
inline char nc(){
static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
if (p1==pend){
if (pend==p1){IOerror=1;return -1;}
//{printf("IO error!\n");system("pause");for (;;);exit(0);}
}
return *p1++;
}
inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
bool sign=0; char ch=nc(); x=0;
for (;blank(ch);ch=nc());
if (IOerror)return;
if (ch=='-')sign=1,ch=nc();
for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
if (sign)x=-x;
}
bool sign=0; char ch=nc(); x=0;
for (;blank(ch);ch=nc());
if (IOerror)return;
if (ch=='-')sign=1,ch=nc();
for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
if (sign)x=-x;
}
bool sign=0; char ch=nc(); x=0;
for (;blank(ch);ch=nc());
if (IOerror)return;
if (ch=='-')sign=1,ch=nc();
for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
if (ch=='.'){
double tmp=1; ch=nc();
for (;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');
}
if (sign)x=-x;
}
char ch=nc();
for (;blank(ch);ch=nc());
if (IOerror)return;
for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch;
*s=0;
}
for (c=nc();blank(c);c=nc());
if (IOerror){c=-1;return;}
}
char ch;int bo=0;x=0;
for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
if (bo)x=-x;
}
char ch;int bo=0;x=0;
for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
if (bo)x=-x;
}
char ch;int bo=0;x=0;
for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
if (ch=='.'){
double tmp=1;
for (ch=getchar();ch>='0'&&ch<='9';tmp/=10.0,x+=tmp*(ch-'0'),ch=getchar());
}
if (bo)x=-x;
}
char ch=getchar();
for (;blank(ch);ch=getchar());
for (;!blank(ch);ch=getchar())*s++=ch;
*s=0;
}
#ifdef _WIN32
scanf("%I64d",&x);
#else
#ifdef __linux
scanf("%lld",&x);
#else
puts("error:can't recognize the system!");
#endif
#endif
}
//fwrite->write
struct Ostream_fwrite{
char *buf,*p1,*pend;
Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
void out(char ch){
if (p1==pend){
fwrite(buf,1,BUF_SIZE,stdout);p1=buf;
}
*p1++=ch;
}
void print(int x){
static char s[15],*s1;s1=s;
if (!x)*s1++='0';if (x<0)out('-'),x=-x;
while(x)*s1++=x%10+'0',x/=10;
while(s1--!=s)out(*s1);
}
void println(int x){
static char s[15],*s1;s1=s;
if (!x)*s1++='0';if (x<0)out('-'),x=-x;
while(x)*s1++=x%10+'0',x/=10;
while(s1--!=s)out(*s1); out('\n');
}
void print(ll x){
static char s[25],*s1;s1=s;
if (!x)*s1++='0';if (x<0)out('-'),x=-x;
while(x)*s1++=x%10+'0',x/=10;
while(s1--!=s)out(*s1);
}
void println(ll x){
static char s[25],*s1;s1=s;
if (!x)*s1++='0';if (x<0)out('-'),x=-x;
while(x)*s1++=x%10+'0',x/=10;
while(s1--!=s)out(*s1); out('\n');
}
void print(double x,int y){
static ll mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,
1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,
100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};
if (x<-1e-12)out('-'),x=-x;x*=mul[y];
ll x1=(ll)floor(x); if (x-floor(x)>=0.5)++x1;
ll x2=x1/mul[y],x3=x1-x2*mul[y]; print(x2);
if (y>0){out('.'); for (size_t i=1;i<y&&x3*mul[i]<mul[y];out('0'),++i); print(x3);}
}
void println(double x,int y){print(x,y);out('\n');}
void print(char *s){while (*s)out(*s++);}
void println(char *s){while (*s)out(*s++);out('\n');}
void flush(){if (p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
~Ostream_fwrite(){flush();}
}Ostream;
inline void print(int x){Ostream.print(x);}
inline void println(int x){Ostream.println(x);}
inline void print(char x){Ostream.out(x);}
inline void println(char x){Ostream.out(x);Ostream.out('\n');}
inline void print(ll x){Ostream.print(x);}
inline void println(ll x){Ostream.println(x);}
inline void print(double x,int y){Ostream.print(x,y);}
inline void println(double x,int y){Ostream.println(x,y);}
inline void print(char *s){Ostream.print(s);}
inline void println(char *s){Ostream.println(s);}
inline void println(){Ostream.out('\n');}
inline void flush(){Ostream.flush();}
//puts->write
char Out[OUT_SIZE],*o=Out;
inline void print1(int x){
static char buf[15];
char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x;
while(x)*p1++=x%10+'0',x/=10;
while(p1--!=buf)*o++=*p1;
}
inline void println1(int x){print1(x);*o++='\n';}
inline void print1(ll x){
static char buf[25];
char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x;
while(x)*p1++=x%10+'0',x/=10;
while(p1--!=buf)*o++=*p1;
}
inline void println1(ll x){print1(x);*o++='\n';}
inline void print1(char c){*o++=c;}
inline void println1(char c){*o++=c;*o++='\n';}
inline void print1(char *s){while (*s)*o++=*s++;}
inline void println1(char *s){print1(s);*o++='\n';}
inline void println1(){*o++='\n';}
inline void flush1(){if (o!=Out){if (*(o-1)=='\n')*--o=0;puts(Out);}}
struct puts_write{
~puts_write(){flush1();}
}_puts;
inline void print2(int x){printf("%d",x);}
inline void println2(int x){printf("%d\n",x);}
inline void print2(char x){printf("%c",x);}
inline void println2(char x){printf("%c\n",x);}
inline void print2(ll x){
#ifdef _WIN32
printf("%I64d",x);
#else
#ifdef __linux
printf("%lld",x);
#else
puts("error:can't recognize the system!");
#endif
#endif
}
inline void println2(ll x){print2(x);printf("\n");}
inline void println2(){printf("\n");}
#undef ll
#undef OUT_SIZE
#undef BUF_SIZE
};

—————————— UPD 2017.7.5 ——————————

static const int BUF_SIZE = 1000000;
static char buf[BUF_SIZE], *p1 = 0, *p2 = 0;
if (p1 == p2){
p2 = (p1 = buf) + fread(buf, 1, BUF_SIZE, stdin);
}
return p1 == p2? -1: *p1++;
}

char c = Read(); int ret = 0, f = 1;
for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = Read());
for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = Read());
return ret * f;
}

## 【模板库】斜堆

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<vector>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 100000+9;

LL vout;
int led[N],n,m,arr[N],rt;
vector<int> G[N];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
return ret*f;
}

namespace Skew_Heap{
#define SHP Skew_Heap
int ch[N][2],sz[N],val[N],root[N],cnt;
LL sum[N];

inline void maintain(int w) {
sz[w] = sz[ch[w][0]] + sz[ch[w][1]] + 1;
sum[w] = sum[ch[w][0]] + sum[ch[w][1]] + val[w];
}

int Merge(int a, int b){
if (!a || !b) return a+b;
else {
if (val[b] > val[a]) swap(a,b);
ch[a][1] = Merge(ch[a][1],b);
swap(ch[a][0],ch[a][1]); maintain(a);
return a;
}
}

inline void pop(int w){
root[w] = Merge(ch[root[w]][0],ch[root[w]][1]);
}

inline void insert(int w, int v){
val[++cnt] = sum[cnt] = v; sz[cnt] = 1;
root[w] = Merge(root[w],cnt);
}
};

int main(){
using namespace Skew_Heap;
for (int i=1,tmp;i<=n;i++) {
}
for (int i=n;i;i--) {
for (int j=0,lim=G[i].size();j<lim;j++) root[i] = Merge(root[i],root[G[i][j]]);
insert(i,arr[i]); while (root[i] && sum[root[i]] > m) pop(i);
vout = max(vout,(LL)sz[root[i]]*led[i]);
}
printf("%lld\n",vout);
return 0;
}

## 【模板库】Fenwick Tree RMQ version

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 200000+9;
const int INF = 1000000000;

int n,m;
char pat[10];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
return ret*f;
}

namespace Fenwick_Tree{
#define BIT Fenwick_Tree
#define lowbit(x) ((x)&(-(x)))
int MX[N],arr[N];

inline void init(){
for (int i=1;i<=n;i++)
MX[i] = -INF;
}

inline void modify(int pos, int val){
int pre = arr[pos]; arr[pos] = val;
if (val >= pre) {
for (int i=pos;i<=n;i+=lowbit(i))
MX[i] = max(MX[i],val);
} else {
for (int i=pos;i<=n;i+=lowbit(i)) {
MX[i] = arr[i];
for (int j=lowbit(i)/2;j;j>>=1)
MX[i] = max(MX[i],MX[i-j]);
}
}
}

inline int query(int l, int r) {
int ret = -INF;
while (r >= l) {
if (r-lowbit(r)+1 >= l) ret = max(ret, MX[r]), r -= lowbit(r);
else ret = max(ret, arr[r]), r--;
}
return ret;
}
};

int main(){
while (~scanf("%d%d",&n,&m)) {
BIT::init();
for (int i=1,l,r;i<=m;i++) {
scanf("%s",pat+1);
}
}
return 0;
}

## 【模板库】Borůvka’s algorithm

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define pow(x) ((x)*(x))
using namespace std;

const int N = 1000+9;
const int M = 1000000+9;
const double EPS = 1e-8;

double w[M],cpt[N],MX;

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline void AddEdge(int i, int j){
double tmp = sqrt(pow(X[i]-X[j])+pow(Y[i]-Y[j]));
to[++m] = j; nxt[m] = head[i]; w[m] = tmp; head[i] = m;
to[++m] = i; nxt[m] = head[j]; w[m] = tmp; head[j] = m;
}

inline int find(int w){
int f=fa[w],tmp;
while (fa[f] != f) f = fa[f];
while (w != f) tmp=fa[w],fa[w]=f,w=tmp;
return f;
}

inline void Boruvka(){
for (int i=1;i<=n;i++) fa[i] = i;
for (int t=n;t>1;) {
memset(cot,0,sizeof(cot));
for (int i=1,f1,f2;i<=n;i++) for (int j=head[i];j;j=nxt[j]){
f1 = find(i); f2 = find(to[j]);
if (f1 != f2) {
if (!cot[f1] || cpt[f1] > w[j]) cot[f1] = f2, cpt[f1] = w[j];
if (!cot[f2] || cpt[f2] > w[j]) cot[f2] = f1, cpt[f2] = w[j];
}
}

for (int i=1,ft;i<=n;i++) if (fa[i] == i) {
if ((ft = find(cot[i])) != i) {
fa[ft] = i; MX = max(MX, cpt[i]); t--;
}
}
}
}

int main(){
n = read(); for (int i=1;i<=n;i++) {
}
Boruvka();
for (int i=1;i<=tot;i++) if (EPS+val[i] >= MX) vout++;
printf("%d\n",vout);
return 0;
}

## 【模板库】对拍

@echo off
:rep
echo running SJ.exe
SJ.exe > 11input.in
echo running bc.exe
bc.exe < 11input.in > 12bc.out
echo running me.exe
me.exe < 11input.in > 12me.out
fc 12me.out 12bc.out > nul
if not errorlevel 1 goto rep

#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<windows.h>
using namespace std;

int main(){
time_t a,b;
while (true) {
system("SJ.exe > 11input.in");

a = clock();
system("bc.exe < 11input.in > 12bc.out");
b = clock(); printf("bc.exe cost %dms\n",b-a);

a = clock();
system("me.exe < 11input.in > 12me.out");
b = clock(); printf("me.exe cost %dms\n",b-a);

int tmp = system("fc 12bc.out 12me.out > result.txt");
if (tmp == 1) system("taskkill /F /IM check.exe");
cout<<endl<<endl;
}
return 0;
}

## 【模板库】仙人掌生成

#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<vector>
using namespace std;

const int N = 10000;
const int Q = 10000;
const int INF = 10000;
const int block = 200;
const int MAXN = 100000;

int ord[MAXN],tmp,cnt,TMP;
vector<pair<int,int> > que;

inline int R(int lim) {
if (!lim) return 0;
else return rand()%lim+1;
}

int main(){
srand(time(0));
int n = N, q=R(Q);
for (int i=1;i<=n;i++) ord[i] = i;
for (int i=1;i<=n;i++) swap(ord[R(n)],ord[R(n)]);
for (int i=1;i<=n;) {
int len = min(R(n/block)+2,n-i+1);
for (int j=0;j<len-1;j++) que.push_back(make_pair(ord[i+j],ord[i+j+1]));
if (len > 2) que.push_back(make_pair(ord[i],ord[i+len-1]));
if (tmp) que.push_back(make_pair(ord[i+R(len)-1],tmp));
tmp = ord[i+R(len)-1]; i += len;
} cnt = que.size();
printf("%d %d %d\n",n,cnt,q);
for (int i=0;i<cnt;i++) {
int a = que[i].first;
int b = que[i].second;
int c = R(INF);
printf("%d %d %d\n",a,b,c);
}
for (int i=1;i<=q;i++)
cout<<R(n)<<' '<<R(n)<<endl;
return 0;
}