板子

*

交题前检查是否爆 long long

是否关了同步流，endl 非交互不出现

空间有没有开够

极限数据关 #define int long long

多组输入记得清空

改过的代码交之前一定过一遍样例

对于数组 $a[i][j][k]$ 保证 $i<=j<=k$ 运行会更快

$s.size()$ 不要直接使用，或代入运算，先赋值到变量里面再用，容易出奇怪错误

// 一些可能会用到的数据范围：$2^{17}=131072$ 大于 1e5；$2^{18}=262144$ 大于 2e5；$2^{20}=1048576$ 大于 1e6；$2^{30}$ 大于 1e9。

二级结论&trick

$1$. 勾股数

$a^n+b^n=c^n$ 仅在 $n==1$ 或者 $n==2$ 时有成立项

当 $n==2$ 时（勾股数）

当 $a$ 为大于 $1$ 的奇数 $2n+1$ 时，$b=2n^2+2n=2n(n+1)$， $c=2n^2+2n+1=2n(n+1)+1$。

当 $a$ 为大于 $4$ 的偶数 $2n$ 时，$b=n^2-1$，$c=n^2+1$。

$2$. 循环节

裴蜀定理可以知道，如果有 $n$ 个数首尾相连，间隔为 $k$ 的走，那么会形成循环节，这样的循环节一共有 $gcd(n,k)$ 个，每个循环节长度 $n/gcd(n,k)$ 个。（且循环节首尾相连）

$3$. 125的倍数的特征：最后 $3$ 位构成的三位数能被 $125$ 整除。

$4$. 重新定义加法和乘法，令小于 $p$ 的非负整数 $m$ 和 $n$，满足 $(m+n)^p=m^p+n^p$，p为质数。

$5$. 欧拉公式：在一个平面中 $V-E+F=2$，其中 $V$ 是全部的顶点数，$E$ 是所有的边数，$F$ 是分割后的平面数。

任意四个点可以有一个交点： $V=n+C^4_n$

$E=C^2_n+2*C^4_n$

$F=C^2_n+C^4_n-n+2$

给你一个正 $n$ 边形，将 $n$ 个顶点两两连边，问内部有多少个区域。因为不算 $n$ 边形外面的区域，所以是 $ans=C^2_n+C^4_n-n+1$。

$6$. 构成一个三角形，只需要保证让任意两边之和大于第三边即可，可以不用考虑两边之差小于第三边。

$7$. $(x+1)^2=x^2+2*x+1$ 可用作递推。

$8$. $Ramsey$ 定理 – 世界上任意 $6$ 个人中，总有 $3$ 个人相互认识，或互相皆不认识。

$9$. 对于 $a_1,a_2,a_3,...,a_i,a_{i+1}$ 这个数组，满足所有的 $a_{i+1}-a_i(i\in[i,n])$，可以推出 $a_i-i=a_j-j$，也就是所有的元素值减去下标值相等。

$10$. 对于一个含有多种括号类型的已匹配括号序列，如果有大于等于三个连续相同类型的括号，或者连续相同类型的括号对数大于等于三，那么这个序列的匹配方式不唯一（当且仅当其不存在长度大于等于 $3$ 的连续段，且存在不超过 $2$ 个长度大于等于 $2$ 的连续段）。

$11$. 把一个数组里所有元素都变得相同至少需要几次操作？这是 一个经典问题，把所有数都变成中位数即可（如果长度为偶数，则中间两个数取平均值）。

$set$ 维护中位数

我们开两个 $multiset$ $s1$, $s2$ 来分别维护大于中位数和小于中位数的数

先来思考查询的方式：

(1)：如果当前窗口内的元素数量之和是偶数，那么中位数就是 $(s1.rbegin()+s2.begin())/2$

(2)：如果当前窗口内的元素数量之和是奇数，那么中位数就是 $s2.begin()$ (后面讲述原因)

再来考虑插入的方式：

(1)：如果两个 $multiset$ 都为空，那么就优先往 $s2$ 里面插入元素

(2)：如果当前元素大于等于 $s2.begin()$，那就把元素插入 $s2$，否则插入 $s1$

由于 $s2.size()$ 始终大于等于 $s1.size()$ 所以奇数情况的中位数就是 $s2.begin()$

我们要使得中位数符合我们的预期，那么两个 $multiset$ 的元素数量之差不能超过 $1$，所以我们需要一个 $balance$ 操作，使得两个 $multiset$ 平衡：

(1)：如果 $s2$ 的元素数量大于 $s1$ 的元素数量 $+1$，那就把 $s2.begin()$ 转移到 $s1$ 中

(2)：如果 $s1$ 的元素数量大于 $s2$ 的元素数量，那就把 $s1.rbegin()$ 转移到 $s2$ 中（注意不要忘了从原 $multiset$ 删除）

为什么会出现 $s1$ 的元素数量大于 $s2$ ?

因为在滑动窗口滑动的过程中，我们删除左端点的时候无法确定是在 $s1$ 还是 $s2$ 中

最后就是如何计算滑动窗口中元素改成中位数的贡献了

我们用两个变量 $sum1$，$sum2$ 分别记录 $s1$，$s2$ 的元素值之和，那么贡献就是 $(s1.size()*mid)-sum1+sum2-(s2.size()*mid)$

因为 $s1$ 中都是小于中位数 $mid$ 的数字，$s2$ 中都是大于等于中位数 $mid$ 的数字

s.extract()

$12$. 数组和 $STL$ 一定要开全局变量，重复开局部变量巨慢。

$13$. 异或运算的性质：$a-b<=a\oplus b<=a+b$

$14$. 蛇形矩阵和回形矩阵

++

#include<bits/stdc++.h>
using namespace std;
const int N = 2e3+5;
int n, m;
char c[N][N];
int dx[8] = {0, 1, 1, -1, 0, 1, 0, -1}, dy[8] = {1, -1, 0, 1, 1, 0, -1, 0};
bool st[N][N];
string s;
void init()
{
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            st[i][j] = false;
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    while(cin >> n)
    {
        s = "";
        init();
        for(int i = 1; i <= n; i ++)
        {
            for(int j = 1; j <= n; j ++)
            {
                cin >> c[i][j];
            }
        }
        // 蛇形矩阵
        // 回形矩阵是一直走到头，转弯。
        // 蛇形矩阵也是四个方向，正右和正下只走一步，两外两个方向一直走到头。
        // 本质上其实和回形矩阵一个写法，只需要判断一下方向来决定只走一步还是一直走到头
        int nx = 1, ny = 1;
        s += c[1][1];
        st[1][1] = true;
        while(1)
        {
            for(int i = 0; i < 4; i ++)
            {
                int x, y;
                if(i == 0 || i == 2)
                {
                    x = dx[i] + nx, y = dy[i] + ny;
                    if(x < 1 || x > n || y < 1 || y > n || st[x][y]) continue;
                    nx = x, ny = y;
                    s += c[nx][ny];
                    st[nx][ny] = true;
                }
                else
                {
                    while(1)
                    {
                        x = dx[i] + nx, y = dy[i] + ny;
                        if(x < 1 || x > n || y < 1 || y > n || st[x][y]) break;
                        nx = x, ny = y;
                        s += c[nx][ny];
                        st[nx][ny] = true;
                    }
                }
            }
            if(nx == n && ny == n) break;
        }
        init();
        // 回形矩阵
        st[1][1] = true;
        nx = 1, ny = 1;
        int now = 0;
        c[1][1] = s[0];
        while(1)
        {
            for(int i = 4; i < 8; i ++)
            {
                int x, y;
                while(1)
                {
                    x = dx[i] + nx, y = dy[i] + ny;
                    if(x < 1 || x > n || y < 1 || y > n || st[x][y]) break;
                    nx = x, ny = y;
                    now ++;
                    c[nx][ny] = s[now];
                    st[nx][ny] = true;
                }
            }
            if(now >= n * n - 1) break;
        }
        
        for(int i = 1; i <= n; i ++)
        {
            for(int j = 1; j <= n; j ++)
            {
                cout << c[i][j];
            }
            cout << '\n';
        }
    }
}

$15$. 枚举一个数二进制串的子集

vector <int> v; for (i = m; i; i = (i - 1) & m) v.push_back(i);

$vector$ 存的 $m$ 的所有子集，$m\oplus i$ 即 $i$ 对于 $m$ 的另外一半补集

$16$. 求 $n$ 元集合中的所有 $k$ 元子集

数论

组合数

预处理结果

#include <iostream>

using namespace std;

const int N = 2010, mod = 1e9 + 7;

int n;
int c[N][N];

void init()
{
    for (int i = 0; i < N; ++ i)
        for (int j = 0; j <= i; ++ j) // 注意这里要求j<=i，所以能够处理所有边界情况。从实际意义上来将，从i个物品中选，最多选择i个，同样能够表示j的范围的意义
            if (!j) c[i][j] = 1; // c_i^0都等于0
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
int main()
{
    init();
    cin >> n;
    while (n --)
    {
        int a, b;
        cin >> a >> b;
        cout << c[a][b] << endl;
    }
    return 0;
}

预处理阶乘和逆元

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int Max = 0x3f3f3f3f3f3f3f3f;
const int Min = -0x3f3f3f3f3f3f3f3f;
const int N = 2e5+5;
typedef pair<int, int>PII;
int T, n, m;
const int mod = 1e9 + 7;
int fact[N], infact[N];

int qpow(int a, int b, int mod)
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
void init()
{
    fact[0] = infact[0] = 1;
    fact[1] = infact[1] = 1;
    for (int i = 1; i < N; ++ i) 
    {
        fact[i] = fact[i - 1] * i % mod;
        // infact[i] = qpow(fact[i], mod - 2, mod); // lg(n) 求逆元
    }
    // 线性求逆元
    for(int i = 2; i < N; i ++)
    {
        infact[i] = (mod - mod / i) * infact[mod % i] % mod;
    }
    for(int i = 2; i < N; i ++)
    {
        infact[i] = infact[i-1] * infact[i] % mod;
    }
}

int C(int a, int b)
{
    if(a < b || b < 0) return 0;
    return fact[a] * infact[b] % mod * infact[a - b] % mod;
}

int A(int a, int b)
{
    if(a < b || b < 0) return 0;
    return fact[a] * infact[a - b] % mod;
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    init();
    cout << C(n, m) << '\n';
    return 0;
}

卢卡斯优化

#include <iostream>

using namespace std;

typedef long long LL;

int n;

int qpow(int a, int b, int p)
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        b >>= 1;
    }
    return res;
}
int c(int a, int b, int p) // 调用组合数时候就一定保证a和b是小于p的了，所以a和b定为int
{
    if (b > a) return 0;
    
    // 按照公式计算
    int res = 1;
    for (int i = a - b + 1, j = 1; j <= b; ++ i, ++ j)
    {
        res = (LL)res * i % p;
        // 保证b是小于p的，因为p质数，所以1到b的所有数都一定与p互质，所以计算逆元可以采用费马小定理
        res = (LL)res * qpow(j, p - 2, p) % p; // 理解原理需要用到“预处理中间值-代码实现”中提到的等式
    }
    
    return res;
}
int lucas(LL a, LL b, int p)
{
    if (a < p && b < p) return c(a, b, p);
    return (LL)c(a % p, b % p, p) * lucas(a / p, b / p, p) % p; // %p保证运算后的结果小于p，无法再使用lucas优化了，所以直接调用组合式函数即可，但/运算则无法保证
}
int main()
{
    cin >> n;
    while (n --)
    {
        int p;
        LL a, b;
        cin >> a >> b >> p;
        
        cout << lucas(a, b, p) << endl;
    }
    return 0;
}

计算卡特兰数

只需要按照公式计算即可，实际采用的是卢卡斯优化代码中组合数的求解方法

#include <iostream>

using namespace std;

typedef long long LL;

const int mod = 1e9 + 7;

int qpow(int a, int b, int mod)
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = (LL)res * a % mod;
        a = (LL)a * a % mod;
        b >>= 1;
    }
    return res;
}
int main()
{
    int n;
    cin >> n;
    
    int res = 1;
    for (int i = n + 1, j = 1; j <= n; ++ i, ++ j)
    {
        res = (LL)res * i % mod;
        res = (LL)res * qpow(j, mod - 2, mod) % mod;
    }
    
    res = (LL)res * qpow(n + 1, mod - 2, mod) % mod;
    
    cout << res << endl;
    return 0;
}

三分

浮点数三分

int tri_search(int l, int r)
{
    // 浮点三分
    const double EPS = 1e-9;
    while (r - l > EPS)
    {
        double lmid = l + (r - l) / 3;
        double rmid = r - (r - l) / 3;
        double f1 = check(lmid), f2 = check(rmid);
        // 求凹函数的极小值
        if (f1 <= f2)
            r = rmid;
        else
            l = lmid;
        // 求凸函数的极大值
        if (f1 >= f2)
            l = lmid;
        else
            r = rmid;
    }
    // 输出 l 或 r 都可
    return l;
}

如果 $f(l) < f(r)$ 说明凸点在 $l$ 右边，如果 $f(r) < f(l)$ 说明凸点在 $r$ 左边

#define eps 10e-6 // 整数三分把eps去掉就好
double f() {} //计算题目所需要的值
while(l+eps<r)
{
    m1=l+(r-l)/3;
    m2=r-(r-l)/3;
    if(f(m1)<f(m2))l=m1;
    else r=m2;
}

牛客的某个题

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 7;
int n;
array<int, 4> a[N];
int check(int t)
{
    int xl = 1e10, xr = -1e10, yl = 1e10, yr = -1e10;
    for (int i = 1; i <= n; i++)
    {
        auto &[x, y, dx, dy] = a[i];
        int xx = x + dx * t;
        int yy = y + dy * t;
        xl = min(xl, xx);
        xr = max(xr, xx);
        yl = min(yl, yy);
        yr = max(yr, yy);
    }
    // cout<<xl<<" "<<xr<<" "<<yl<<" "<<yr<<"\n";
    return 2 * (xr - xl) + 2 * (yr - yl);
}
int tri_search(int l, int r)
{
    // 求凹函数的极小值
    int f1, f2;
    while (l < r)
    {
        int lp = l + (r - l) / 3;
        int rp = r - (r - l) / 3;
        f1 = check(lp), f2 = check(rp);
        if (f1 <= f2) r = rp - 1;
        else l = lp + 1;
    }
    // 查找的是极小值
    return min(f1, f2);
    // 查找的是极小值对应的下标
    return f1 < f2 ? l : r;
}
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        char op;
        int x, y;
        cin >> x >> y >> op;
        if (op == 'E') a[i] = {x, y, 1, 0};
        else if (op == 'W') a[i] = {x, y, -1, 0};
        else if (op == 'S') a[i] = {x, y, 0, -1};
        else a[i] = {x, y, 0, 1};
    }
    int t = tri_search(0, 3000000000);
    cout << t << "\n";
    // cout<<check(t)<<"\n";
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin>>T;
    while (T--)
    {
        solve();
    }
    return 0;
}

Min_25筛求质数和

范围大概 $10^{11}$ ~ $10^{12}$

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1000010;
int prime[N], id1[N], id2[N], flag[N], ncnt, m;
ll g[N], sum[N], a[N], T;
ll n;
int ID(ll x) {
    return x <= T ? id1[x] : id2[n / x];
}
ll calc(ll x) {
    return x * (x + 1) / 2 - 1;
}
ll f(ll x) {
    return x;
}
void init(ll n){
    T = sqrt(n + 0.5);
    for (int i = 2; i <= T; i++) {
        if (!flag[i]) prime[++ncnt] = i, sum[ncnt] = sum[ncnt - 1] + i;
        for (int j = 1; j <= ncnt && i * prime[j] <= T; j++) {
            flag[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
        }
    }
    for (ll l = 1; l <= n; l = n / (n / l) + 1) {
        a[++m] = n / l;
        if (a[m] <= T) id1[a[m]] = m; else id2[n / a[m]] = m;
        g[m] = calc(a[m]);
    }
    for (int i = 1; i <= ncnt; i++)
        for (int j = 1; j <= m && (ll)prime[i] * prime[i] <= a[j]; j++)
            g[j] = g[j] - (ll)prime[i] * (g[ID(a[j] / prime[i])] - sum[i - 1]);
}
ll solve(ll x){
    if(x<=1){return x;}
    return n=x,init(n),g[ID(n)];
}
int main() {
	int t = 1;
	cin >> t;
    while(t-- ) {
    	memset(g,0,sizeof(g));
    	memset(a,0,sizeof(a));
    	memset(sum,0,sizeof(sum));
    	memset(prime,0,sizeof(prime));
		memset(id1,0,sizeof(id1));
		memset(id2,0,sizeof(id2));
		memset(flag,0,sizeof(flag));
		ncnt=m=0;
		scanf("%lld", &n);
		printf("%lld\n", solve(n));
    }
}

求 n 维向量

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    int T; cin >> T;
    while(T--)
    {
        cin >> n >> k;
        if(n == 1) cout << "1\n";
        else if(n == k || k % 2 == 0) cout << "-1\n";
        else
        {
            // 用define int long long 也注意要把1强制转换，1还是int类型
            cout << (1ll << k) - 1;
            for(int i = k - 1; i >= 0; --i)
            {
 
                ll x = (1ll << (k + 1)) - 1;
                x ^= 1ll << i;
                cout << " " << x;
            }
            for(int i = k + 2; i <= n; ++i)
            {
 
                ll x = 1ll << (i - 1);
                x ^= (1ll << (k - 1)) - 1;
                cout << " " << x;
            }
            cout << "\n";
        }
    }
    return 0;
}

图论

kruskal 重构树

在建立最小生成树时，将边权提取出来，作为新的节点。

比如点 $1$，$2$ 相连，边权为 $1$。那么新开一个节点，编号 $10$。$10$ 连接 $1$，$10$ 连接 $2$。

此时又有点 $1$，$3$ 相连，边权为 $1$。那么再新开一个节点，编号 $11$。$11$ 连接 $10$，$11$ 连接 $3$。

这样就能构建出一颗二叉树。并且从 $1$ 走到 $3$ 最短路径上的最大权值就是编号 $11$ 的权值。也就是说从 $x$ 节点走到 $y$ 节点的最大权值是最近公共祖先的权值。

[ICPC2021 上海 H题 life is a game](Problem - H - Codeforces)

$n$ 个点，$m$ 条边，$k$ 个询问。每个点上有一个权值 $a_i$，经过这个点时可以获得它的权值，每个点的权值只能获取一次。每条边上也有一个权值 $c$，对于点 $i$，$j$。如果当前权值 $w$ 大于边上的权值 $c$，就可以经过这条边。

每个询问给出 $x$ 和 $z$，代表当前位于 $x$ 点上，初始权值是 $z$。对每个询问求出可获得的最大权值。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+5;
int n, m, k;
int p[N], a[N], lg[N];
int f[N][20], c[N][20];
struct node
{
    int x, y, z;
}tr[N];

int find(int x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}
bool cmp(node aa, node bb)
{
    return aa.z < bb.z;
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m >> k;
    for(int i = 1; i <= 2*n; i ++) p[i] = i;
    for(int i = 2; i <= 2*n; i ++) lg[i] = lg[i >> 1] + 1;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
    }
    for(int i = 1; i <= m; i ++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        tr[i] = {x, y, z};
    }
    sort(tr + 1, tr + m + 1, cmp);
    int cnt = n;
    for(int i = 1; i <= m; i ++)
    {
        int x = tr[i].x, y = tr[i].y, z = tr[i].z;
        int px = find(x), py = find(y);
        if(px == py) continue;
        cnt ++;
        p[px] = cnt;
        p[py] = cnt;
        a[cnt] = a[px] + a[py];
        f[px][0] = f[py][0] = cnt;
        c[px][0] = z - a[px];
        c[py][0] = z - a[py];
    }
    for(int j = 1; j <= lg[cnt]; j ++)
    {
        for(int i = 1; i <= cnt; i ++)
        {
            f[i][j] = f[f[i][j-1]][j-1];
            c[i][j] = max(c[i][j-1], c[f[i][j-1]][j-1]); // 得到的是路径上的最大值
        }
    }
    a[0] = a[cnt];    // 最顶端的点（初始化）
    while(k --)
    {
        int x, z;
        cin >> x >> z;
        for(int i = lg[cnt]; i >= 0; i --)
        {
            if(z >= c[x][i]) x = f[x][i];
        }
        cout << a[x] + z << '\n';
    }
    return 0;
}

次短路

开一个二维数组 $dis[N][2]$ 分别记录最短路和次短路即可。推荐 $spfa$

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
typedef long long ll;
int n, m, k;
int T;
struct node
{
    int e, w;
};
vector<node>v[N];
int dis[N][2];
bool st[N];
queue<int>q;
 
void spfa()
{
    memset(dis, 0x3f, sizeof dis);
    dis[n][0] = 0;
    q.push(n);
    st[n] = true;
    while(q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        for(int i = 0; i < v[t].size(); i ++)
        {
            int z = v[t][i].e;
            if(dis[z][0] > dis[t][0] + v[t][i].w)
            {
                dis[z][1] = dis[z][0];
 
                dis[z][0] = dis[t][0] + v[t][i].w;
                if(!st[z])
                {
                    q.push(z);
                    st[z] = true;
                }
            }
            if(dis[z][1] > dis[t][0] + v[t][i].w&&dis[z][0] < dis[t][0] + v[t][i].w)
            {
                dis[z][1] = dis[t][0] + v[t][i].w;
                if(!st[z])
                {
                    q.push(z);
                    st[z] = true;
                }
            }
            if(dis[z][1] > dis[t][1] + v[t][i].w)
            {
                dis[z][1] = dis[t][1] + v[t][i].w;
                if(!st[z])
                {
                    q.push(z);
                    st[z] = true;
                }
            }
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> m;
    while(m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }
    spfa();
    cout << dis[1][1] << "\n";
    return 0;
}

分层图

由于可以任意走动，所以我们可以建一张图，令图上的边全都是 $0$ ，表示我的走动对我最终的结果没有影响。

考虑某个点 $i$，它买入或者卖出水晶球的花费是 $v_i$。

那么： 当我们进行买入操作，我们就建立一条有向边转移到一张新图上，边的大小为 $-v_i$ ，它从第一层的点 $i_{0}$ 指向第二层的点 $i_{1}$ 。而这张新图就是我们的第二层图。

它表示：假如我选择走了这条边，就是我在这个点买了这个水晶球，我不会反悔，并且我接下来考虑在某个点卖它。

当我们进行卖出操作，我们建立一条有向边转移到第三层图上，边的大小为 $v_i$，它从第二层的点 $i_{1}$ 指向第三层的点 $i_{2}$。

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+5;
typedef long long ll;
typedef pair<int, int>PII;
int n, m, k;
int T;
queue<int>q;
struct node
{
    int e, w;
};
vector<node>v[N];
bool st[N];
int dis[N];

void spfa()
{
    for(int i = 1; i <= 3*n; i ++) dis[i] = INT_MIN;
    dis[1] = 0;
    q.push(1);
    st[1] = true;

    while(q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        for(int i = 0; i < v[t].size(); i ++)
        {
            int z = v[t][i].e;
            if(dis[z] < dis[t] + v[t][i].w)
            {
                dis[z] = dis[t] + v[t][i].w;
                if(!st[z])
                {
                    q.push(z);
                    st[z] = true;
                }
            }
        }
    }
}
/*分层图，三层 */
void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        int x;
        cin >> x;
        v[i].push_back({i + n*1, -x});
        v[i+n*1].push_back({i + n*2, x});
    }
    while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({b, 0});
        v[a+n*1].push_back({b+n*1, 0});
        v[a+n*2].push_back({b+n*2, 0});
        if(c==2) v[b].push_back({a, 0}), v[b+n*1].push_back({a+n*1, 0}), v[b+n*2].push_back({a+n*2, 0});
    }

    spfa();
    cout << dis[3*n];

}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    T = 1;
    while(T --)
    {
        solve();
    }
    return 0;
}

差分约束

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
typedef long long ll;
typedef pair<int, int>PII;
int n, m, k;
int T;
queue<int>q;
int dis[N], cnt[N];
bool st[N];
struct node
{
    int e, w;
};
vector<node>v[N];

bool spfa()
{
    memset(dis, 0x3f3f3f3f, sizeof dis);
    dis[0] = 0;
    q.push(0);
    st[0] = true;

    while(q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;

        for(int i = 0; i < v[t].size(); i ++)
        {
            int z = v[t][i].e;
            if(dis[z] > dis[t] + v[t][i].w)
            {
                cnt[z] = cnt[t] + 1;
                if(cnt[z] > n) return true;
                dis[z] = dis[t] + v[t][i].w;
                if(!st[z])
                {
                    st[z] = true;
                    q.push(z);
                }
            }
        }
    }
    return false;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) v[0].push_back({i, 0});
    while(m --)
    {
        int x;
        cin >> x;
        if(x==1)
        {
            int a, b, c;
            cin >> a >> b >> c;
            v[a].push_back({b, -c});
        }
        else if(x==2)
        {
            int a, b, c;
            cin >> a >> b >> c;
            v[b].push_back({a, c});
        }
        else 
        {
            int a, b;
            cin >> a >> b;
            v[a].push_back({b, 0}), v[b].push_back({a, 0});
        }
    }
    if(spfa()) cout << "No\n";
    else cout << "Yes\n";
    return 0;
}

同余最短路

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int, int>
const int N = 1e5+5;
int n, m, k;
int dis[N];
bool st[N];
priority_queue<PII, vector<PII>, greater<PII>>q;
vector<PII>v[N];

void dijkstra()
{
	q.push({0, 0});
	dis[0] = 0;
	while(q.size())
	{
		PII t = q.top();
		q.pop();
		int t1 = t.first, t2 = t.second;
		if(st[t2]) continue;
		st[t2] = true;
		for(int i = 0; i < v[t2].size(); i ++)
		{
			int z = v[t2][i].first;
			if(dis[z] > dis[t2] + v[t2][i].second)
			{
				dis[z] = dis[t2] + v[t2][i].second;
				q.push({dis[z], z});
			}
		}
	}
}

signed main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	memset(dis, 0x3f, sizeof dis);
	cin >> n;
	int a[3];
	cin >> a[0] >> a[1] >> a[2];
	sort(a, a + 3);
	if(a[0]==1)
	{
		cout << n;
		return 0;
	}
	for(int i = 0; i < a[0]; i ++)
	{
		v[i].push_back({(i+a[1])%a[0], a[1]});
		v[i].push_back({(i+a[2])%a[0], a[2]});
	}
	dijkstra();
	int ans = 0;
	for(int i = 0; i < a[0]; i ++)
	{
		if(dis[i]<=n-1)
		ans+=(n-1-dis[i])/a[0]+1;
	}
	cout << ans << "\n";
	return 0;
}

最短路径唯一，输出经过点

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
typedef long long ll;
int r1[505], r[505];
int cnt[505], path[505];
int dis[505];
int v[505][505];
bool st[505];
int n, m, k, s, d;
int T;

void find(int u)
{
    if(path[u]!=-1)
    {
        find(path[u]);
        cout << path[u] << " ";
    }
}

void dijkstra(int u)
{
    dis[u] = 0;
    r[u] = r1[u];
    for(int i = 0; i < n; i ++)
    {
        int t = -1;
        for(int j = 0; j < n; j++)
        {
            if(!st[j]&&(t==-1||dis[t]>dis[j]))
                t = j;
        }
        if(t==-1) break;
        st[t] = true;
        for(int j = 0; j < n; j ++)
        {
            if(dis[j] > dis[t] + v[t][j])
            {
                dis[j] = dis[t] + v[t][j];
                cnt[j] = cnt[t];
                path[j] = t;
                r[j] = r[t] + r1[j];
            }
            else if(dis[j] == dis[t] + v[t][j])
            {
                cnt[j]+=cnt[t];
                if(r[j] < r[t]+r1[j])
                {
                    r[j] = r[t]+r1[j];
                    path[j] = t;
                }
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> m >> s >> d;
    memset(dis, 0x3f, sizeof dis);
    memset(v, 0x3f, sizeof v);
    memset(path, -1, sizeof path);
    for(int i = 0; i < n; i ++) cnt[i] = 1;
    for(int i = 0; i < n; i ++)
    {
        cin >> r1[i];
    }
    while(m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        v[a][b] = v[b][a] = c;
    }
    dijkstra(s);
    cout << cnt[d] << " "<<r[d]<<"\n";
    find(d);
    cout << d;
    return 0;
}

网络流

最大流

EK

($O(nm^2)$)，据说一般适用于 $10^3$~$10^4$ 规模的网络

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+5;
int n, m, s, t;
int h[N], e[N], ne[N], idx;
int cf[N], mf[N], pre[N]; // 分别是这个边的容量、s~v的流量上限、v的前驱边
queue<int>q;

void add(int a, int b, int c)
{
    e[idx] = b, cf[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int bfs()
{
    for(int i = 1; i <= n; i ++) mf[i] = 0;
    while(q.size()) q.pop();
    q.push(s);
    mf[s] = 1e18;
    while(q.size())
    {
        int u = q.front();
        q.pop();
        for(int i = h[u]; i != -1; i = ne[i])
        {
            int v = e[i];
            if(mf[v] == 0 && cf[i])
            {
                mf[v] = min(mf[u], cf[i]);
                pre[v] = i;
                q.push(v);
                if(v == t) return true;
            }
        }
    }
    return false;
}

int EK()
{
    int flow = 0;
    while(bfs())
    {
        int v = t;
        while(v != s)
        {
            int i = pre[v];
            cf[i] -= mf[t];
            cf[i^1] += mf[t];
            v = e[i^1];
        }
        flow += mf[t];
    }
    return flow;
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m >> s >> t;
    for(int i = 1; i <= n; i ++) h[i] = -1;
    for(int i = 0; i < m; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, 0);
    }
    cout << EK() << '\n';
}

dinic（适用更广）

（$O(n^2m)$），据说一般适用于 $10^4$~$10^5$ 规模的网络

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+5;
int n, m, s, t;
int h[N], e[N], ne[N], idx;
int cf[N]; // 边的容量
int d[N]; // 点深度，做分层图
int cur[N]; // 当前弧

queue<int>q;

void add(int a, int b, int c)
{
    e[idx] = b, cf[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int bfs() //对点分层，找增广路
{
    for(int i = 1; i <= n; i ++) d[i] = 0;
    while(q.size()) q.pop();
    q.push(s);
    d[s] = 1;
    while(q.size())
    {
        int u = q.front();
        q.pop();
        for(int i = h[u]; i != -1; i = ne[i])
        {
            int v = e[i];
            if(d[v] == 0 && cf[i])
            {
                d[v] = d[u] + 1;
                q.push(v);
                if(v == t) return true;
            }
        }
    }
    return false;
}

int dfs(int u, int mf) // 多路增广
{
    if(u == t) return mf;
    int sum = 0;
    for(int i = cur[u]; ~i; i = ne[i])
    {
        cur[u] = i; // 当前弧优化
        int v = e[i];
        if(d[v] == d[u] + 1 && cf[i])
        {
            int f = dfs(v, min(mf, cf[i]));
            cf[i] -= f;
            cf[i^1] += f; // 更新残留网
            sum += f; // 累加u的流出流量
            mf -= f; // 减少u的剩余流量
            if(mf == 0) break; //余量优化
        }
    }
    if(sum == 0) d[u] = 0;
    return sum;
}

int dinic()
{
    int flow = 0;
    while(bfs())
    {
        memcpy(cur, h, sizeof h); // 把数组h赋值给cur
        flow += dfs(s, 1e18);
    }
    return flow;
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m >> s >> t;
    for(int i = 1; i <= n; i ++) h[i] = -1;
    for(int i = 0; i < m; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, 0);
    }
    cout << dinic() << '\n';
}

LCA

倍增法、$tarjan$、树链剖分

题目：$n$ 个点，$m$ 个询问，$s$ 是根节点

倍增求 LCA

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
int n, m, s;
int dep[N], fa[N][20];
vector<int>v[N];

void dfs(int u, int f)
{
    dep[u] = dep[f] + 1;
    fa[u][0] = f;
    for(int i = 1; i < 20; i ++)
    {
        fa[u][i] = fa[fa[u][i-1]][i-1];
    }
    for(int e : v[u])
    {
        if(e != f) dfs(e, u);
    }
}

int lca(int x, int y)
{
    if(dep[x] < dep[y]) swap(x, y);    // 让 x 的深度大于等于 y
    for(int i = 19; i >= 0; i --)
    {
        if(dep[fa[x][i]] >= dep[y]) x = fa[x][i];   // 跳到同一深度
    }
    if(x == y) return x;
    for(int i = 19; i >= 0; i --)    // 一块向上跳，直到父节点相同
    {
        if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
    }
    return fa[x][0];
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m >> s;
    for(int i = 1; i < n; i ++)
    {
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(s, 0);
    for(int i = 1; i <= m; i ++)
    {
        int x, y;
        cin >> x >> y;
        cout << lca(x, y) << '\n';
    }
    return 0;
}

tarjan 求 LCA（并查集）

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
typedef pair<int, int>PII;
int n, m, s;
vector<int>v[N];
vector<PII>q[N];
int p[N], ans[N];
bool st[N];

int find(int x)
{
    if(x == p[x]) return x;
    return p[x] = find(p[x]);
}
void tj(int u)
{
    st[u] = true;
    for(int e : v[u])
    {
        if(!st[e])
        {
            tj(e);
            p[e] = u;
        }
    }
    for(PII it : q[u])
    {
        int t1 = it.first, t2 = it.second;
        if(st[t1]) ans[t2] = find(t1);
    }
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m >> s;
    for(int i = 1; i < n; i ++)
    {
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i = 1; i <= m; i ++)     // 离线处理
    {
        int x, y;
        cin >> x >> y;
        q[x].push_back({y, i});
        q[y].push_back({x, i});
    }
    for(int i = 1; i <= n; i ++) p[i] = i;  // 并查集初始化不要忘
    tj(s);
    for(int i = 1; i <= m; i ++)
    {
        cout << ans[i] << '\n';
    }
}

重链剖分求 LCA

轻儿子一定是重链的头节点

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
int n, m, s;
vector<int>e[N];
// 子树大小，父节点，重链顶点，重儿子，深度
int sz[N], fa[N], top[N], son[N], dep[N];

void dfs1(int u, int f)  // 主要是为了求出每个节点的深度和重儿子
{
    sz[u] = 1, fa[u] = f, dep[u] = dep[f] + 1;
    for(int v : e[u])
    {
        if(v == f) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if(sz[son[u]] < sz[v]) son[u] = v;
    }
}

void dfs2(int u, int t)
{
    top[u] = t;
    if(!son[u]) return;
    dfs2(son[u], t);
    for(int v : e[u])
    {
        if(v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

int lca(int u, int v)
{
    while(top[u] != top[v])
    {
        if(dep[top[u]] < dep[top[v]]) swap(u, v); //始终让 u 最深
        u = fa[top[u]];
    }
    return dep[u] < dep[v] ? u : v;
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m >> s;    // n 个点， m 个询问， s 是根节点
    for(int i = 1; i < n; i ++)
    {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs1(s, 0);
    dfs2(s, s);
    for(int i = 1; i <= m; i ++)
    {
        int x, y;
        cin >> x >> y;
        int tt = lca(x, y);
        cout << tt << '\n';
    }
    return 0;
}

tarjan

时间戳 $dfn_i$ 节点 $i$ 第一次被访问的顺序

追溯值 $low_i$ 从节点 $i$ 出发，所能访问到的最早时间戳

最大强连通分量

缩点模板题

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int Max = 0x3f3f3f3f3f3f3f3f;
const int Min = -0x3f3f3f3f3f3f3f3f;
const int N = 2e5+5;
typedef pair<int, int>PII;
int T, n, m;
vector<int>v[N], nv[N];
int a[N];
int dfn[N], tot = 0, low[N], sk[N], cnt, top;
int scc[N], w[N], sz[N];
bool vis[N];
int din[N], res[N];
queue<int>q;

void tj(int u)
{
    dfn[u] = low[u] = ++tot;
    vis[u] = true;
    sk[++top] = u;
    for(int e : v[u])
    {
        if(!dfn[e])
        {
            tj(e);
            low[u] = min(low[u], low[e]);
        }
        else if(vis[e])
        {
            low[u] = min(low[u], dfn[e]);
        }
    }
    if(low[u] == dfn[u])
    {
        int e; ++cnt;
        do{
            e = sk[top --];
            scc[e] = cnt;
            sz[cnt] ++;
            vis[e] = false;
            w[cnt] += a[e];
        }while(e != u);
    }
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
    }

    for(int i = 1; i <= m; i ++)
    {
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
    }
    for(int i = 1; i <= n; i ++)
    {
        if(!dfn[i]) tj(i);
    }
    for(int i = 1; i <= n; i ++)    // 缩点建新图
    {
        for(int j : v[i])
        {
            if(scc[i] != scc[j])
            {
                nv[scc[i]].push_back(scc[j]);
                din[scc[j]] ++;
            }
        }
    }

    for(int i = 1; i <= cnt; i ++)
    {
        res[i] = w[i];
        if(!din[i]) q.push(i);
    }
    while(q.size())    // 拓扑排序求最大权值路径
    {
        int t = q.front();
        q.pop();
        for(int e : nv[t])
        {
            din[e] --;
            res[e] = max(res[e], res[t] + w[e]);
            if(din[e] == 0)
            {
                q.push(e);
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i ++)
    {
        ans = max(ans, res[i]);
    }
    cout << ans << '\n';
    return 0;
}

割点

割点：对于一个无向图，如果把一个点删除后，连通块的个数增加了，那么这个点就是割点(又称割顶)。

割点判定法则：

（1）如果 $x$ 不是根节点，当搜索树上存在 $x$ 的一个子节点 $y$，满足 $low[y]≥dfn[x]$，那么 $x$ 就是割点。

（2）如果 $x$ 是根节点，当搜索树上存在至少两个子节点 $y1$，$y2$，满足上述条件，那么 $x$ 就是割点。

重边和自环不影响割点判定

题目：给出一个 n 个点，m 条边的无向图，求图的割点。

第一行输出割点个数。

第二行按照节点编号从小到大输出节点，用空格隔开。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int n, m;
vector<int>v[N];
int res = 0, ls[N];
bool vis[N];
int dfn[N], low[N], tot = 0, rt;

void tj(int u)
{
    dfn[u] = low[u] = ++tot;
    int cnt = 0;
    for(int e : v[u])
    {
        if(!dfn[e])
        {
            tj(e);
            low[u] = min(low[u], low[e]);
            if(low[e] >= dfn[u])
            {
                cnt ++;
                if(u != rt || cnt > 1)   // 根节点的话，要求子树个数大于一
                {
                    vis[u] = true;
                }
            }
        }
        else low[u] = min(low[u], dfn[e]);
    }
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i ++)
    {
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i = 1; i <= n; i ++)
    {
        if(!dfn[i])
        {
            rt = i;
            tj(i);
        }
    }

    for(int i = 1; i <= n; i ++)
        if(vis[i]) ls[++res] = i;

    cout << res << '\n';
    for(int i = 1; i <= res; i ++)
        cout << ls[i] << " \n"[i == n];
    return 0;
}

割边

割边：对于一个无向图，如果删掉一条边后图中的连通块个数增加了，则称这条边为桥或者割边。

割边判定法则：当搜索树上存在 x 的一个子节点 y，满足 $low[y]>dfn[x]$，则 $(x,y)$ 这条边就是割边。

题目：n 个点，m 条边，求出图中的所有割边，按字典序从小到大输出

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int n, m;
int h[N], e[N], ne[N], idx = 1; // 建图编号从1开始，h数组不用初始化-1了
int dfn[N], low[N], tot = 0;
set<pair<int, int>>se;

void add(int a, int b)
{
    e[++ idx] = b, ne[idx] = h[a], h[a] = idx;
}

void tj(int u, int x)
{
    dfn[u] = low[u] = ++tot;
    for(int i = h[u]; i; i = ne[i])
    {
        int t = e[i];
        if(!dfn[t])
        {
            tj(t, i);
            low[u] = min(low[u], low[t]);
            if(low[t] > dfn[u])  // 题目要求输出最小的字典序，所以用的set
            {
                int a = t, b = u;
                if(a > b) swap(a, b);
                se.insert({a, b});
            }
        }
        else if(i != (x ^ 1))
        {
            low[u] = min(low[u], dfn[t]);
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i ++)
    {
        int x, y;
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }
    for(int i = 1; i <= n; i ++)
    {
        if(!dfn[i]) tj(i, 0);
    }
    for(auto it : se)
    {
        cout << it.first << " " << it.second << '\n';
    }
    return 0;
}

eDCC 缩点（边双连通分量）

边双连通分量的含义：无向图中极大的不包含割边的连通块

如果求边双连通分量内点的数量，只需要遍历 $scc$ 即可，求边的数量则去遍历 $bri$

for(int i = 2; i <= idx; i += 2)
    {
        if(bri[i])     // 建图
        {
            int x = scc[e[i]], y = scc[e[i ^ 1]];
            v[x].push_back(y);
            v[y].push_back(x);
        }
        else
        {
            sz[scc[e[i]]] ++; // 存的是编号为scc[e[i]]的边双连通分量内边的数量
        }
    }

题目：POJ3177

大意：给定一个连通的无向图让你进行加边操作，要求每一对点之间都至少有两条相互分离的路径，求最小的加边数。注：两条路径相互分离是指两条路径没有一条重合的道路。

做法：Tarjan 一遍，标记割边，记录 $eDCC$。将 $eDCC$ 缩点，得到一棵树，树边就是原图的割边。观察发现,最少需要加 $(sum+1)/2$ 条边，可以使整个图变为边的双连通图。$sum$ 为缩点后叶节点的个数。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int n, m;
int e[N], ne[N], h[N], idx = 1;
int dfn[N], low[N], tot;
bool bri[N];
int sk[N], top;
int dcc[N], cnt = 0, du[N];

void add(int x, int y)
{
    e[++ idx] = y, ne[idx] = h[x], h[x] = idx;
}

void tj(int u, int id)
{
    dfn[u] = low[u] = ++tot;
    sk[++top] = u;
    for(int i = h[u]; i; i = ne[i])
    {
        int t = e[i];
        if(!dfn[t])
        {
            tj(t, i);
            low[u] = min(low[u], low[t]);
            if(low[t] > dfn[u])    // 割边操作，把割边记录下来（也就是桥）
            {
                bri[i] = true;
                bri[i ^ 1] = true;
            }
        }
        else if(i != (id ^ 1))
        {
            low[u] = min(low[u], dfn[t]);
        }
    }
    if(dfn[u] == low[u])
    {
        int y; cnt ++;
        do{
            y = sk[top --];
            dcc[y] = cnt;
        }while(y != u);
    }
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i ++)
    {
        int x, y;
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }

    for(int i = 1; i <= n; i ++)
    {
        if(!dfn[i]) tj(i, 0);
    }

    for(int i = 2; i <= idx; i ++)
    {
        if(bri[i])
        {
            du[dcc[e[i]]] ++;   // 注意这里不要写成了 du[e[i]] ++
        }
    }
    int res = 0;
    for(int i = 1; i <= cnt; i ++)
    {
        if(du[i] == 1) res ++;
    }
    cout << (res + 1) / 2 << '\n';
    return 0;
}

例题： Problem - H - Codeforces

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6+5;
int n, m;
int e[N], ne[N], h[N], idx = 1, w[N];
int dfn[N], low[N], tot;
bool bri[N];
int sk[N], top;
int dcc[N], cnt = 0, du[N];
int ans = 0, res = 0;
void add(int x, int y, int z) // 编号i的边，两端点是e[i]和e[i^1]
{
    e[++ idx] = y, ne[idx] = h[x], w[idx] = z, h[x] = idx;
}

void tj(int u, int id)
{
    dfn[u] = low[u] = ++tot;
    sk[++top] = u;
    for(int i = h[u]; i; i = ne[i])
    {
        int t = e[i];
        if(!dfn[t])
        {
            tj(t, i);
            low[u] = min(low[u], low[t]);
            if(low[t] > dfn[u])  
            {
                bri[i] = true;
                bri[i ^ 1] = true;
            }
        }
        else if(i != (id ^ 1))
        {
            low[u] = min(low[u], dfn[t]);
        }
    }
    if(dfn[u] == low[u])
    {
        int y; cnt ++;
        do{
            y = sk[top --];
            dcc[y] = cnt;
        }while(y != u);
    }
}
vector<int>v[N];
int sz[N];

void dfs(int u, int f)
{
    for(int it : v[u])
    {
        if(it == f) continue;
        dfs(it, u);
        sz[u] += sz[it] + 1;
    }
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i ++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
        add(y, x, z);
        res += z;
    }
    if(m % 2 == 0)
    {
        cout << res << '\n';
        return 0;
    }
    for(int i = 1; i <= n; i ++)
    {
        if(!dfn[i]) tj(i, 0);
    }
    for(int i = 2; i <= idx; i += 2) // i和(i^1)是同一条边，计算一条就行
    {
        if(bri[i])
        {
            int t1 = dcc[e[i]], t2 = dcc[e[i^1]]; // 建立新图的时候，一定要用连通块编号
            v[t1].push_back(t2);
            v[t2].push_back(t1);
        }
        else
        {
            sz[dcc[e[i]]] ++;
            sz[dcc[e[i^1]]] ++;
            ans = max(ans, res - w[i]);
        }
    }
    for(int i = 1; i <= cnt; i ++) sz[i] /= 2; // 统计的是每个连通块内边的数量，每个边被统计了两边，所以除以2
    dfs(1, 0);
    for(int i = 2; i <= idx; i += 2)
    {
        if(bri[i])
        {
            int t1 = dcc[e[i]], t2 = dcc[e[i^1]];
            int zz = min(sz[t1], sz[t2]);
            if(zz % 2 == 0) ans = max(ans, res - w[i]);
        }
    }
    cout << ans << '\n';
}

vDCC 缩点（点双连通分量）

$n$ 个点，$m$ 条边，缩点之后的图。样例：

8 10
1 2
2 3
3 4
2 4
1 4
1 5
5 6
5 7
5 8
7 8

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int n, m;
int rt, id[N], cnt, num;
int dfn[N], low[N], tot;
stack<int>sk;
vector<int>v[N], nv[N], dcc[N];
bool cut[N];

void tj(int u)
{
    dfn[u] = low[u] = ++ tot;
    sk.push(u);
    if(v[u].size() == 0)
    {
        dcc[++cnt].push_back(u);
        return;
    }   
    int ct = 0;
    for(int e : v[u])
    {
        if(!dfn[e])
        {
            tj(e);
            low[u] = min(low[u], low[e]);
            if(low[e] >= dfn[u])
            {
                ct ++;
                if(u != rt || ct > 1) cut[u] = true;
                cnt ++;
                while(1)
                {
                    int z = sk.top(); sk.pop();
                    dcc[cnt].push_back(z);
                    if(z == e) break;
                }
                dcc[cnt].push_back(u);
            }
        }
        else low[u] = min(low[u], dfn[e]);
    }
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    while(m --)
    {
        int x, y;
        cin >> x >> y;
        if(x == y) continue;  // 判自环
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i = 1; i <= n; i ++)
    {
        if(!dfn[i])
        {
            rt = i;
            tj(i);
        }
    }
    num = cnt;
    for(int i = 1; i <= n; i ++)
    {
        if(cut[i])id[i] = ++num;
    }
    for(int i = 1; i <= cnt; i ++)
    {
        for(int j = 0; j < dcc[i].size(); j ++)
        {
            int x = dcc[i][j];
            if(cut[x])
            {
                nv[i].push_back(id[x]);
                nv[id[x]].push_back(i);
            }
        }
    }
    for(int i = 1; i <= cnt; i ++)
    {
        cout << i << " -- ";
        for(auto j : nv[i])
        {
            cout << j << " ";
        }
        cout << '\n';
    }
    return 0;
}

tarjan 题(2021 沈阳 H)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int Max = 0x3f3f3f3f3f3f3f3f;
const int Min = -0x3f3f3f3f3f3f3f3f;
const int N = 4e5+5;
typedef pair<int, int>PII;
int n, m;
int idx = 1, e[N], ne[N], h[N], w[N];
int sz[N];
bool bri[N];
vector<int>v[N];

void add(int a, int b, int c)
{
    e[++ idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx;
}

int dfn[N], low[N], tot = 0, sk[N], cnt = 0, top = 0, scc[N];

void tj(int u, int x)
{
    dfn[u] = low[u] = ++ tot;
    sk[++ top] = u;
    for(int i = h[u]; i; i = ne[i])
    {
        int t = e[i];
        if(!dfn[t])
        {
            tj(t, i);
            low[u] = min(low[u], low[t]);
            if(low[t] > dfn[u])
            {
                bri[i] = true;
                bri[i ^ 1] = true;
            }
        }
        else if(i != (x ^ 1))
        {
            low[u] = min(low[u], dfn[t]);
        }
    }
    if(low[u] == dfn[u])
    {
        int x; ++ cnt;
        do{
            x = sk[top --];
            scc[x] = cnt;
        }while(x != u);
    }
}
void dfs(int u, int f)
{
    for(int j : v[u])
    {
        if(j == f) continue;
        dfs(j, u);
        sz[u] += sz[j] + 1;
    }
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    int res = 0;
    for(int i = 1; i <= m; i ++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
        add(y, x, z);
        res += z;
    }
    if(m % 2 == 0)
    {
        cout << res << '\n';
        return 0;
    }
    for(int i = 1; i <= n; i ++)
    {
        if(!dfn[i]) tj(i, 0);
    }
    int ans = 0;
    for(int i = 2; i <= idx; i += 2)
    {
        if(bri[i])
        {
            int x = scc[e[i]], y = scc[e[i ^ 1]];
            v[x].push_back(y);
            v[y].push_back(x);
        }
        else
        {
            sz[scc[e[i]]] ++;
            ans = max(ans, res - w[i]);
        }
    }
    dfs(1, 0);
    for(int i = 2; i <= idx; i += 2)
    {
        if(bri[i])
        {
            int x = sz[scc[e[i]]], y = sz[scc[e[i ^ 1]]];
            x = min(x, y);
            if(x % 2 == 0)
            {
                ans = max(ans, res - w[i]);
            }
        }
    }
    cout << ans << '\n';
}

数据结构

单链表

#include <iostream>
using namespace std;
const int N = 100010;

// head 表示头结点的下标
// e[i] 表示节点i的值
// ne[i] 表示节点i的next指针是多少
// idx 存储当前已经用到了哪个点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 将x插到头结点
void add_to_head(int x)
{
    e[idx] = x, ne[idx] = head, head = idx ++ ;
}

// 将x插到下标是k的点后面
void add(int k, int x)
{
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++ ;
}

// 将下标是k的点后面的点删掉
void remove(int k)
{
    ne[k] = ne[ne[k]];
}

int main()
{
    int m;
    cin >> m;
    
    init();

    while (m -- )
    {
        int k, x;
        char op;
        cin >> op;
        if (op == 'H')
        {
            cin >> x;
            add_to_head(x);
        }
        else if (op == 'D')
        {
            cin >> k;
            if (!k) head = ne[head];
            else remove(k - 1);
        }
        else
        {
            cin >> k >> x;
            add(k - 1, x);
        }
    }
    for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
    cout << '\n';
    return 0;
}

双链表

#include <iostream>
using namespace std;
const int N = 100010;
int m;
int e[N], l[N], r[N], idx;

// 在节点a的右边插入一个数x
void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}

// 删除节点a
void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}

int main()
{
    cin >> m;

    // 0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;

    while (m -- )
    {
        string op;
        cin >> op;
        int k, x;
        if (op == "L") //L x，表示在链表的最左端插入数 x
        {
            cin >> x;
            insert(0, x);
        }
        else if (op == "R") // R x，表示在链表的最右端插入数 x
        {
            cin >> x;
            insert(l[1], x);
        }
        else if (op == "D") // 表示将第 k 个插入的数删除
        {
            cin >> k;
            remove(k + 1);
        }
        else if (op == "IL") // 表示在第 k 个插入的数左侧插入一个数
        {
            cin >> k >> x;
            insert(l[k + 1], x);
        }
        else                 // 表示在第 k 个插入的数右侧插入一个数
        {
            cin >> k >> x;
            insert(k + 1, x);
        }
    }
    for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';
    cout << '\n';
    return 0;
}

ST 表

// for(int i = 2; i <= n; i ++) lg[i] = lg[i >> 1] + 1; // 预处理

void ST(int n)
{
    // 初始化
    for (int i = 1; i <= n; i++)
        f[i][0] = a[i];
    // 从第i个数起连续2^j个数中的最大值
    for (int j = 1; (1 << j) <= n; j++) 
        for (int i = 1; i + (1 << j) - 1 <= n; i++) // 注意边界，1 << j 就是2的j次幂
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}

int RMQ(int l, int r)
{
    int s = Log2[r - l + 1]; // log2(r - l + 1)下取整
    return max(f[l][s], f[r - (1 << s) + 1][s]);
}

权值线段树

求逆序对

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 4e5+5;
int T, n, m;
int a[N], tr[N * 4], s[N];
vector<int>v;

int getid(int x)
{
    return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

void pushup(int u)
{
    tr[u] = tr[u << 1] + tr[u << 1 | 1];
}

void updata(int x, int l, int r, int u)
{
    if(l == x && r == x)
    {
        tr[u] ++;
        return;
    }
    int mid = l + r >> 1;
    if(x <= mid) updata(x, l, mid, u << 1);
    else updata(x, mid + 1, r, u << 1 | 1);
    pushup(u);
}

int query(int x, int y, int l, int r, int u)
{
    if(l >= x && r <= y)
    {
        return tr[u];
    }
    int mid = l + r >> 1;
    int res = 0;
    if(x <= mid) res += query(x, y, l, mid, u << 1);
    if(y > mid) res += query(x, y, mid + 1, r, u << 1 | 1);
    return res; 
}

void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    for(int i = 1; i <= n; i ++)
    {
        v.push_back(s[i]);
        v.push_back(s[i] + m);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    int n2 = v.size();
    int ans = 0;
    for(int i = 1; i <= n; i ++)
    {
        int x = getid(s[i]);
        ans += query(x + 1, n2, 1, n2, 1);
        int y = getid(s[i] + m);
        updata(y, 1, n2, 1);
        if(s[i] < m) ans ++;
    }
    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();    
}

扫描线

相当于一个权值线段树，下面的代码是以y坐标排序，扫描线从下至上扫描。将 $n$ 条线的 $2n$ 个 $x$ 坐标离散化。例如当一条线两端的x坐标为 $x_1$ 和 $x_2$，那么就让 $x_1$ 一直到 $x_2$ 这整个区间的出现次数加一或者减一，出现次数大于 $0$ 就代表存在这个边长。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5+5;
int T, n, m, sz = 0, ans = 0;
vector<int> v;
struct node
{
    int l, r, len, tot;
}tr[N * 4];

struct blde
{
    int x, x2, y, f;
}bl[N * 4];

bool cmp(blde aa, blde bb)
{
    return aa.y < bb.y;
}
void build(int u, int l, int r)
{
    tr[u] = {l, r, 0, 0};
    if(l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}

void pushup(int u)
{
    int l = tr[u].l, r = tr[u].r;
    // 传参左偏，计算右偏，因为v下标从0开始，所以都减去了1
    if(tr[u].tot) tr[u].len = v[r + 1 - 1] - v[l - 1];
    else tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
}

void modify(int u, int l, int r, int k)
{
    if(tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].tot += k;
        pushup(u);
        return;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if(mid >= l) modify(u << 1, l, r, k);
    if(mid + 1 <= r) modify(u << 1 | 1, l, r, k);
    pushup(u);
}

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        int x, y, x2, y2;
        cin >> x >> y >> x2 >> y2;
        v.push_back(x), v.push_back(x2);
        bl[i] = {x, x2, y, 1};
        bl[i + n] = {x, x2, y2, -1};
    }
    n *= 2; // 这里乘了2，用板子时注意
    sort(bl + 1, bl + n + 1, cmp);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    sz = v.size();
    build(1, 1, sz - 1);  // 因为左偏一位，所以减去一个

    for(int i = 1; i < n; i ++)
    {
        int t1 = lower_bound(v.begin(), v.end(), bl[i].x) - v.begin() + 1;
        int t2 = lower_bound(v.begin(), v.end(), bl[i].x2) - v.begin() + 1;
        modify(1, t1, t2 - 1, bl[i].f);   // 传参左偏，计算右偏
        ans += tr[1].len * (bl[i+1].y - bl[i].y);
    }
    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    T = 1;
    while(T --)
    {
        solve();
    }
}

可持久化字典树

最大异或和

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 600010, M = N * 25;

int n, m;
int s[N];
int tr[M][2], max_id[M];
int root[N], idx;

void insert(int i, int k, int p, int q)
{
    if (k < 0)
    {
        max_id[q] = i;
        return;
    }
    int v = s[i] >> k & 1;
    if (p) tr[q][v ^ 1] = tr[p][v ^ 1];
    tr[q][v] = ++ idx;
    insert(i, k - 1, tr[p][v], tr[q][v]);
    max_id[q] = max(max_id[tr[q][0]], max_id[tr[q][1]]);
}

int query(int root, int C, int L)
{
    int p = root;
    for (int i = 23; i >= 0; i -- )
    {
        int v = C >> i & 1;
        if (max_id[tr[p][v ^ 1]] >= L) p = tr[p][v ^ 1];
        else p = tr[p][v];
    }

    return C ^ s[max_id[p]];
}

int main()
{
    scanf("%d%d", &n, &m);

    max_id[0] = -1;
    root[0] = ++ idx;
    insert(0, 23, 0, root[0]);

    for (int i = 1; i <= n; i ++ )
    {
        int x;
        scanf("%d", &x);
        s[i] = s[i - 1] ^ x;
        root[i] = ++ idx;
        insert(i, 23, root[i - 1], root[i]);
    }

    char op[2];
    int l, r, x;
    while (m -- )
    {
        scanf("%s", op);
        if (*op == 'A')
        {
            scanf("%d", &x);
            n ++ ;
            s[n] = s[n - 1] ^ x;
            root[n] = ++ idx;
            insert(n, 23, root[n - 1], root[n]);
        }
        else
        {
            scanf("%d%d%d", &l, &r, &x);
            printf("%d\n", query(root[r - 1], s[n] ^ x, l - 1));
        }
    }

    return 0;
}

可持久化线段树（主席树）

插入

int updata(int p, int l, int r, int x) // p是上一个版本的根节点，[l,r]是当前值域，x是插入值
{
    int q = ++ idx;
    tr[q] = tr[p];   // 先将上一节点信息直接赋值
    if (l == r)
    {
        tr[q].cnt ++ ;
        return q;
    }
    int mid = l + r >> 1;
    if (x <= mid) tr[q].l = updata(tr[p].l, l, mid, x);
    else tr[q].r = updata(tr[p].r, mid + 1, r, x);
    tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
    return q;
}

查询

如果是 $[1,r]$ 区间，就是权值线段树的做法，插入 $r$ 个数后直接询问第 $k$ 小即可。

对于 $[l,r]$ 区间，利用前缀和的思想，用版本 $r$ 减去版本 $l-1$ 就得到了 $[l,r]$ 区间的情况。

区间第 k 小

$n$ 个值的数组，$m$ 次询问区间 $[l,r]$ 的第 $k$ 小

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int n, m;
int a[N], root[N], idx;
vector<int> v;

struct Node
{
    int l, r;
    int cnt;
}tr[N * 4 + N * 17];    // 空间大小 N * (logN + 5) 绝对够用

int get(int x)
{
    return lower_bound(v.begin(), v.end(), x) - v.begin();
}

int build(int l, int r)
{
    int p = ++ idx;
    if (l == r) return p;
    int mid = l + r >> 1;
    tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);
    return p;
}

int updata(int p, int l, int r, int x)
{
    int q = ++ idx;
    tr[q] = tr[p];
    if (l == r)
    {
        tr[q].cnt ++ ;
        return q;
    }
    int mid = l + r >> 1;
    if (x <= mid) tr[q].l = updata(tr[p].l, l, mid, x);
    else tr[q].r = updata(tr[p].r, mid + 1, r, x);
    tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
    return q;
}

int query(int q, int p, int l, int r, int k)
{
    if (l == r) return r;
    int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
    int mid = l + r >> 1;
    if (k <= cnt) return query(tr[q].l, tr[p].l, l, mid, k);
    else return query(tr[q].r, tr[p].r, mid + 1, r, k - cnt);
}

signed main()
{
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> a[i];
        v.push_back(a[i]);
    }

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    root[0] = build(0, v.size() - 1);

    for (int i = 1; i <= n; i ++ )
        root[i] = updata(root[i - 1], 0, v.size() - 1, get(a[i]));

    while (m -- )
    {
        int l, r, k;
        cin >> l >> r >> k;
        cout << v[query(root[r], root[l - 1], 0, v.size() - 1, k)] << '\n';
    }
    return 0;
}

线段树动态开点

下面代码是求区间最大值，修改操作是对于 $val$ 位置上增加 $delta$

struct node
{
	int lc, rc; // 左右子节点的编号
	int dat; // 区间最大值
}tr[N * 4];
int root, tot;

int build()  // 新建一个节点
{
	tot ++;
	tr[tot].lc = tr[tot].rc = tr[tot].dat = 0;
	return tot;
}

void insert(int p, int l, int r, int val, int delta)
{
    if(l == r)
    {
        tr[p].dat += delta;
        return;
    }
    int mid = l + r >> 1;  // 代表的区间[l,r]作为递归参数传递
    if(val <= mid)
    {
        if(!tr[p].lc) tr[p].lc = build();  // 动态开点
        insert(tr[p].lc, l, mid, val, delta);
    }
    else
    {
        if(!tr[p].rc) tr[p].rc = build();
        insert(tr[p].rc, mid + 1, r, val, delta);
    }
    tr[p].dat = max(tr[tr[p].lc].dat, tr[tr[p].rc].dat); // push_up 操作
}

// 在main函数中
tot = 0;
root = build();  // 根节点
insert(root, 1, n, val, delta); // 调用

树链剖分

重链剖分

先进入轻子树，算完轻子树答案后记录，然后清空轻子树，将根节点下的轻子树全部跑完并清空。

最后跑重子树，算完重子树答案后记录，并且不清空重子树。

回溯到根节点，再此遍历根节点下的轻子树去更新根节点答案，重子树不需要遍历，因为上次遍历过后并没有清空重子树的数据。

Problem - E - Codeforces（计算各个子树内节点的颜色权值和）

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int Max = 0x3f3f3f3f3f3f3f3f;
const int Min = -0x3f3f3f3f3f3f3f3f;
const int N = 2e5+5;
typedef pair<int, int>PII;
int T, n, m;
int sz[N], son[N], fa[N];
vector<int>v[N];
int col[N], cnt[N], ans[N];
int sum, mx;

void dfs(int u, int f) // 预处理，求出重儿子
{
    sz[u] = 1;
    for(int e : v[u])
    {
        if(e == f) continue;
        dfs(e, u);
        sz[u] += sz[e];
        if(sz[son[u]] < sz[e]) son[u] = e;
    }
}

void add(int u, int f, int son)
{
    cnt[col[u]] ++;
    if(cnt[col[u]] > mx)
    {
        mx = cnt[col[u]];
        sum = col[u];
    }
    else if(cnt[col[u]] == mx)
    {
        sum += col[u];
    }
    for(int e : v[u])
    {
        if(e == f || e == son) continue;
        add(e, u, son);
    }
}

void sub(int u, int f)
{
    cnt[col[u]] --;
    for(int e : v[u])
    {
        if(e == f) continue;
        sub(e, u);
    }
}

void dsu(int u, int f, int c)
{
    for(int e : v[u])
    {
        if(e == f || e == son[u]) continue;
        dsu(e, u, 0); 
    }
    if(son[u]) dsu(son[u], u, 1);
    add(u, f, son[u]);
    ans[u] = sum;
    if(!c) sub(u, f), sum = mx = 0;
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> col[i];
    }
    for(int i = 1; i < n; i ++)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1, 0);
    dsu(1, 0, 0);
    for(int i = 1; i <= n; i ++) cout << ans[i] << " ";
}

Problem - F - Codeforces

给一颗无向树，根为 $1$。对于每个节点，求其子树中，哪个距离下的节点数量最多。数量相同时，取较小的那个距离。

dus on tree，统计每个子树中相同深度的最大值即可，$ans[u]=pos-dep[u]$。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int n, m;
int sz[N], son[N], dep[N];
vector<int>v[N];
int ans[N], cnt[N];
int mx, pos;

void dfs(int u, int f)
{
    dep[u] = dep[f] + 1;
    sz[u] = 1;
    for(int e : v[u])
    {
        if(e == f) continue;
        dfs(e, u);
        sz[u] += sz[e];
        if(sz[son[u]] < sz[e]) son[u] = e;
    }
}

void add(int u, int f, int son)
{
    cnt[dep[u]] ++;
    if(cnt[dep[u]] > mx || (cnt[dep[u]] == mx && dep[u] < pos))
    {
        mx = cnt[dep[u]];
        pos = dep[u];
    }
    for(int e : v[u])
    {
        if(e == f || e == son) continue;
        add(e, u, son);
    }
}

void sub(int u, int f)
{
    cnt[dep[u]] --;
    for(int e : v[u])
    {
        if(e == f) continue;
        sub(e, u);
    }
}

void dsu(int u, int f, int z)
{
    for(int e : v[u])
    {
        if(e == f || e == son[u]) continue;
        dsu(e, u, 0);
    }
    if(son[u]) dsu(son[u], u, 1);
    add(u, f, son[u]);
    ans[u] = pos - dep[u];
    if(!z) sub(u, f), mx = 0, pos = 0;
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1; i < n; i ++)
    {
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1, 0);
    dsu(1, 0, 0);
    for(int i = 1; i <= n; i ++)
    {
        cout << ans[i] << '\n';
    }
    return 0;
}

Problem - D - Codeforces（计算子树回文串最大长度）

Arpa has a rooted tree (connected acyclic graph) consisting of n vertices. The vertices are numbered 1 through n, the vertex 1 is the root. There is a letter written on each edge of this tree. Mehrdad is a fan of Dokhtar-kosh things. He call a string Dokhtar-kosh, if we can shuffle the characters in string such that it becomes palindrome.

He asks Arpa, for each vertex v, what is the length of the longest simple path in subtree of v that form a Dokhtar-kosh string.

The first line contains integer n (1  ≤  n  ≤  $5·10^5$) — the number of vertices in the tree.

(n  -  1) lines follow, the i-th of them contain an integer $p^{i + 1}$ and a letter $c^{i + 1}$ (1  ≤  $p^{i + 1}$  ≤  i, $c^{i + 1}$ is lowercase English letter, between a and v, inclusively), that mean that there is an edge between nodes $p^{i + 1}$ and i + 1 and there is a letter $c^{i + 1}$written on this edge.

Print n integers. The i-th of them should be the length of the longest simple path in subtree of the i-th vertex that form a Dokhtar-kosh string.

写法一：$dfs$

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5+5;
typedef pair<int, int>PII;
int T, n, m;
vector<PII>v[N];
int sz[N], dep[N], dis[N], fa[N], son[N], ans[N];
int ju[1 << 22]; // ju[i] 存的是值为 i 时的最大深度
void dfs(int u, int f)
{
    sz[u] = 1;
    dep[u] = dep[f] + 1;
    for(auto it : v[u])
    {
        int t = it.first, w = it.second;
        if(t == f) continue;
        fa[t] = u;
        dis[t] = dis[u] ^ w;
        dfs(t, u);
        sz[u] += sz[t];
        if(sz[son[u]] < sz[t]) son[u] = t;
    }
}

void updata(int u, int f)
{
    ju[dis[u]] = max(ju[dis[u]], dep[u]);
    for(auto it : v[u])
    {
        int t = it.first;
        if(t == f) continue;
        updata(t, u);
    }
}

void add(int u, int f, int son, int to) // to 是当前子树的根节点
{
    // dis[u] ^ dis[v] = 0
    if(ju[dis[u]]) ans[to] = max(ans[to], ju[dis[u]] + dep[u] - 2 * dep[to]);
    // dis[u] ^ dis[v] = 1 << k;
    for(int i = 0; i < 22; i ++)
        if(ju[dis[u] ^ (1 << i)])
            ans[to] = max(ans[to], dep[u] + ju[dis[u] ^ (1 << i)] - 2 * dep[to]);
    // 头节点算完就能立刻更新，后面算子树的时候先算完子树才能更新，不然就乱了
    if(u == to)
    {
        ju[dis[u]] = max(ju[dis[u]], dep[u]);
    }
    for(auto it : v[u])
    {
        int t = it.first;
        if(t != f) ans[u] = max(ans[u], ans[t]); // 将之前的子树答案更新到根节点上，再去算根节点
        if(t == f || t == son) continue;
        add(t, u, son, to);
    }
    // 子树被计算完答案后才能将其权值记录,并将其节点全部更新，不能避开轻子树内的重儿子
    if(fa[u] == to)
    {
        updata(u, f);
    }
}

void sub(int u, int f)
{
    ju[dis[u]] = 0;
    for(auto it : v[u])
    {
        int t = it.first;
        if(t == f) continue;
        sub(t, u);
    }
}

void dsu(int u, int f, int z)
{
    for(auto it : v[u])
    {
        int t = it.first;
        if(t == f || t == son[u]) continue;
        dsu(t, u, 0);
    }
    if(son[u]) dsu(son[u], u, 1);
    add(u, f, son[u], u); // 计算每个子树的答案
    if(!z) sub(u, f); // 清空轻子树
}

void solve()
{
    cin >> n;
    for(int i = 2; i <= n; i ++)
    {
        int x; char c;
        cin >> x >> c;
        int w = 1 << (c - 'a');
        v[x].push_back({i, w});
        v[i].push_back({x, w});
    }
    dfs(1, 0);
    dsu(1, 0, 0);
    for(int i = 1; i <= n; i ++)
    {
        cout << ans[i] << " \n"[i == n];
    }
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    T = 1;
    while(T --)
    {
        solve();
    }
}

写法二：给节点赋值新编号，循环遍历

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define maxn 500005
using namespace std;
int read() {
	int x = 0, f = 1, ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
	return x * f;
}
 
int n;
struct edge {
	int to, w, nxt;
	edge() {}
	edge(int tt, int ww, int nn) {to = tt, w = ww, nxt = nn;}
}e[maxn << 1];
 
int head[maxn], k = 0;
void add(int u, int v, int w) {e[k] = edge(v, w, head[u]); head[u] = k++;}
 
int ans[maxn], siz[maxn], son[maxn], dfn[maxn], maxx[maxn], id[maxn];
int dep[maxn], dis[maxn], tot = 0;
void dfs1(int u) {
	siz[u] = 1; dfn[u] = ++tot; id[tot] = u;//dfn是映射，id是反函数 
	for(int i = head[u]; ~i; i = e[i].nxt) {
		register int v = e[i].to; dep[v] = dep[u] + 1; dis[v] = dis[u] ^ e[i].w;
		dfs1(v);
		siz[u] += siz[v];
		if(siz[son[u]] < siz[v]) son[u] = v;//找重儿子 
	} 
	maxx[u] = tot;//记录字数内映射编号最大的节点的编号 
}

int judge[1 << 22];//桶内存在下边状态下最大的深度。 

void dfs2(int u, bool keep) {
	for(int i = head[u]; ~i; i = e[i].nxt) {
		register int v = e[i].to; if(v != son[u]) dfs2(v, 0), ans[u] = max(ans[u], ans[v]);
	}

	if(son[u]) dfs2(son[u], 1), ans[u] = max(ans[u], ans[son[u]]);
	
    // dis[u] ^ dis[v] = 0;
	if(judge[dis[u]]) ans[u] = max(ans[u], judge[dis[u]] - dep[u]);//两种情况都匹配一下，这里合起来是直链 
    
    // dis[u] ^ dis[v] = 1 << k;
    // 上式可转化为 dis[u] ^ (1 << k) = dis[v]
	for(int i = 0; i < 22; i++) 
		if(judge[dis[u] ^ (1 << i)]) ans[u] = max(ans[u], judge[dis[u] ^ (1 << i)] - dep[u]);

	judge[dis[u]] = max(judge[dis[u]], dep[u]);//把自己的信息存进去 
	for(int i = head[u]; ~i; i = e[i].nxt)
    {
		register int v = e[i].to; if(v == son[u]) continue; //不管重子树的信息，因为存在judge里的所以后面直接用 
		for(int j = dfn[v]; j <= maxx[v]; j++)
        {//枚举各个轻子树的信息并匹配一下 ，以u为lca 
			register int x = id[j];
			if(judge[dis[x]]) ans[u] = max(ans[u], judge[dis[x]] + dep[x] - 2 * dep[u]);
			for(int k = 0; k < 22; k++) 
				if(judge[dis[x] ^ (1 << k)]) ans[u] = max(ans[u], judge[dis[x] ^ (1 << k)] + dep[x] - 2 * dep[u]);
		}
        // 全部枚举过后，才能加入信息, 否则会出现同一子树下两条路径合并重叠。
		for(int j = dfn[v]; j <= maxx[v]; j++) judge[dis[id[j]]] = max(judge[dis[id[j]]], dep[id[j]]);//加入信息 
	}
	if(!keep) for(int i = dfn[u]; i <= maxx[u]; i++) judge[dis[id[i]]] = 0;	//不保留轻儿子 
}

signed main() {
	memset(head, -1, sizeof head);
	n = read(); char op;
	for(int i = 2, v; i <= n; i++) v = read(), cin >> op, add(v, i, 1 <<(op - 'a'));
	
	dfs1(1); //预处理基本树剖信息 
	dfs2(1, 1);
 
	for(int i = 1; i <= n; i++) printf("%d ", ans[i]);
	return 0;
}

长链剖分

待补

字符串

AC自动机

时间复杂度 $O(26n+m)$

回跳边指向父节点的回跳边所指节点的儿子

转移边指向当前节点的回跳边所指节点的儿子

回跳边是指针j走的路径，每次回跳边走的跳到的都是最大后缀，$she$，$he$，$e$ 一直回调到 $0$ 根节点。**转移边走的是最近路径，可以不需要从当前位置回到根节点后重新出发。**转移边借助回跳边建立，是指针 $i$ 走的路径，因为借助回跳边建立，他会回跳到最大后缀的节点中，$she$ 后匹配到r失败，树边上没有这条边，但是回跳边有这条路径，所以转移到 $sher$ 的最大后缀 $her$ 节点处。

$n(10^4)$ 个长度不超过 $50$ 的字符串，检查是否在长度为 $10^6$ 的字符串中出现过

#include<bits/stdc++.h>
using namespace std;
const int N = 10010, S = 55, M = 1000010;
int n;
int tr[N * S][26], cnt[N * S], idx;
string s;
int q[N * S], ne[N * S];

void insert()
{
    int p = 0;
    for (int i = 0; s[i]; i ++ )
    {
        int t = s[i] - 'a';
        if (!tr[p][t]) tr[p][t] = ++ idx;
        p = tr[p][t];
    }
    cnt[p] ++ ;
}

void build()
{
    int hh = 0, tt = -1;
    for (int i = 0; i < 26; i ++ )
        if (tr[0][i])
            q[ ++ tt] = tr[0][i];

    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = 0; i < 26; i ++ )
        {
            int p = tr[t][i];
            if (!p) tr[t][i] = tr[ne[t]][i];
            else
            {
                ne[p] = tr[ne[t]][i];
                q[ ++ tt] = p;
            }
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T -- )
    {
        memset(tr, 0, sizeof tr);
        memset(cnt, 0, sizeof cnt);
        memset(ne, 0, sizeof ne);
        idx = 0;

        cin >> n;
        for (int i = 0; i < n; i ++ )
        {
            cin >> s;
            insert();
        }

        build();

        cin >> s;

        int ans = 0;
        for(int k = 0, i = 0; s[k]; k ++)
        {
            i = tr[i][s[k] - 'a'];
            // 每个串只会统计一次，如果需要统计多次，将~cnt[j]和cnt[j]=-1删除即可
            for(int j = i; j && ~cnt[j]; j = ne[j])
            {
                ans += cnt[j], cnt[j] = -1;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

后缀数组（后缀排序）

$LCP(i,j)$ 为 $suff(sa[i])$ 与 $suff(sa[j])$ 的最长公共前缀

此题目没用到 $lcp$

#include<iostream>
#include<cstdio>
#include<cstring>
#define rint register int
#define inv inline void
#define ini inline int
#define maxn 1000050
using namespace std;
char s[maxn];
int y[maxn],x[maxn],c[maxn],sa[maxn],rk[maxn],height[maxn],wt[30];
int n,m;
inv putout(int x)
{
    if(!x) {putchar(48);return;}
    rint l=0;
    while(x) wt[++l]=x%10,x/=10;
    while(l) putchar(wt[l--]+48);
}
inv get_SA()
{
	for (rint i=1;i<=n;++i) ++c[x[i]=s[i]];
	//c数组是桶 
	//x[i]是第i个元素的第一关键字 
    for (rint i=2;i<=m;++i) c[i]+=c[i-1]; 
    //做c的前缀和，我们就可以得出每个关键字最多是在第几名 
    for (rint i=n;i>=1;--i) sa[c[x[i]]--]=i; 
    for (rint k=1;k<=n;k<<=1)
    {
        rint num=0;
        for (rint i=n-k+1;i<=n;++i) y[++num]=i;
        //y[i]表示第二关键字排名为i的数，第一关键字的位置 
		//第n-k+1到第n位是没有第二关键字的 所以排名在最前面 
        for (rint i=1;i<=n;++i) if (sa[i]>k) y[++num]=sa[i]-k;
        //排名为i的数 在数组中是否在第k位以后
		//如果满足(sa[i]>k) 那么它可以作为别人的第二关键字，就把它的第一关键字的位置添加进y就行了
		//所以i枚举的是第二关键字的排名，第二关键字靠前的先入队 
        for (rint i=1;i<=m;++i) c[i]=0;
        //初始化c桶 
        for (rint i=1;i<=n;++i) ++c[x[i]];
        //因为上一次循环已经算出了这次的第一关键字 所以直接加就行了 
        for (rint i=2;i<=m;++i) c[i]+=c[i-1];//第一关键字排名为1~i的数有多少个 
        for (rint i=n;i>=1;--i) sa[c[x[y[i]]]--]=y[i],y[i]=0;
        //因为y的顺序是按照第二关键字的顺序来排的 
        //第二关键字靠后的，在同一个第一关键字桶中排名越靠后 
        //基数排序 
        swap(x,y);
		//这里不用想太多，因为要生成新的x时要用到旧的，就把旧的复制下来，没别的意思 
        x[sa[1]]=1;num=1;
        for (rint i=2;i<=n;++i)
            x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]) ? num : ++num;
        //因为sa[i]已经排好序了，所以可以按排名枚举，生成下一次的第一关键字 
        if (num==n) break;
        m=num;
        //这里就不用那个122了，因为都有新的编号了 
    }
    for (rint i=1;i<=n;++i) putout(sa[i]),putchar(' ');
}
inv get_height()
{
    rint k=0;
    for (rint i=1;i<=n;++i) rk[sa[i]]=i;
    for (rint i=1;i<=n;++i)  
    {
        if (rk[i]==1) continue;//第一名height为0 
        if (k) --k;//h[i]>=h[i-1]+1;
        rint j=sa[rk[i]-1];
        while (j+k<=n && i+k<=n && s[i+k]==s[j+k]) ++k;
        height[rk[i]]=k;//h[i]=height[rk[i]];
    }
    putchar(10);for (rint i=1;i<=n;++i) putout(height[i]),putchar(' ');
}
int main()
{
    gets(s+1);
    n=strlen(s+1);m=122;
	//因为这个题不读入n和m所以要自己设
	//n表示原字符串长度，m表示字符个数，ascll('z')=122 
	//我们第一次读入字符直接不用转化，按原来的ascll码来就可以了 
	//因为转化数字和大小写字母还得分类讨论，怪麻烦的 
    get_SA();
    //get_height();
}

后缀自动机

#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
int tot=1,las=1;
struct NODE
{
    int ch[26];
    int len,fa;
    NODE(){memset(ch,0,sizeof(ch));len=fa=0;}
}dian[2000010];
struct Edge
{
    int t,nexty;
}edge[2000010];
int head[2000010],cnt=0;
void jia(int a,int b)
{
    cnt++;
    edge[cnt].t=b;
    edge[cnt].nexty=head[a];
    head[a]=cnt;
}
long long zhi[2000010];
inline void add(int c)
{
    register int p=las,np=las=++tot;zhi[tot]=1;
    dian[np].len=dian[p].len+1;
    for(;p&&!dian[p].ch[c];p=dian[p].fa)dian[p].ch[c]=np;
    if(!p)dian[np].fa=1;
    else
    {
        register int q=dian[p].ch[c];
        if(dian[q].len==dian[p].len+1)dian[np].fa=q;
        else
        {
            register int nq=++tot;
            dian[nq]=dian[q];dian[nq].len=dian[p].len+1;
            dian[q].fa=dian[np].fa=nq;
            for(;p&&dian[p].ch[c]==q;p=dian[p].fa)dian[p].ch[c]=nq;
        }
    }
}
char s[2000010];
int cd;
long long ans=0;
void dfs(int node)
{
    for(register int i=head[node];i;i=edge[i].nexty)
    {
        dfs(edge[i].t);
        zhi[node]+=zhi[edge[i].t];
    }
    if(zhi[node]!=1)ans=max(ans,zhi[node]*dian[node].len);
}
int main()
{
    scanf("%s",s);cd=strlen(s);
    for(register int i=0;i<cd;i++)add(s[i]-'a');
    for(register int i=2;i<=tot;i++)jia(dian[i].fa,i);
    dfs(1);
    printf("%lld\n",ans);
    return 0;
}