f[i][j]统一定义为i个小球放到j个盒子里的方案数

1.m^n

2.m!/(m-n)!

3.f[i][j]=j*f[i-1][j]+(m-j+1)*f[i-1][j-1]

  考虑容斥可以O(n)

4.第二类斯特林数S[n][1]+...+S[n][m]

  O(n^2)直接递推S[i][j]=S[i-1][j-1]+j*S[i-1][j]

  O(nlogn)NTT,斯特林数反演

5.[n<=m]

6.S[n][m]

7.C(n+m-1,m-1)

8.C(m,n)

9.C(n-1,m-1)

10.f[i][j]=f[i][j-1]+f[i-j][j]

    考虑球的数量>=根号n的盒子的个数＜=根号n个可以分块O(n^1.5)

    五边形数定理可优化到O(nlogn)

11.[n<=m]

12.f[i][j]=f[i-1][j-1]+f[i-j][j]  自然数拆分

    同10

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19645638

更好的阅读体验（加强版）：https://www.cnblogs.com/To-Carpe-Diem/p/19645952

$\newcommand{\binom}[2]{{#1 \choose #2}}$

大意

$n$ 对情侣，恰好 $k$ 对在 $2 \times n$ 的电影院中坐一起的方案数。

思路

很好的题目，使得我的大脑旋转。

首先我们先定义函数 $f(n, k)$ 表示 $n$ 对情侣有 $k$ 对恰好坐到一块的方案数。首先我们要从 $n$ 对情侣中选择 $k$ 对，这个是 $\binom{n}{k}$ 的，再从 $n$ 排选择 $k$ 排，这个也是 $\binom{n}{k}$ 的，考虑到这 $k$ 对情侣间也有先后顺序，贡献就是 $k!$，两人可以换位，贡献是 $2 ^ k$，剩下有 $n - k$ 对情侣，我们只需要将其错排即可。

定义 $g(m)$ 表示 $m$ 对情侣错排的方案数，我们考虑这个怎么求。这个我们可以利用容斥原理，我们考虑直接计算至少 $j$ 对和睦的方案数，那么这个的贡献与上面的类似，应当是 $\binom{m}{j} ^ 2 j! 2 ^ j (2(m - j))!$，那么由容斥可知：$g(m) = \sum_{j = 0} ^ {m}(-1) ^ j \binom{m}{j} ^ 2 j! 2 ^ j (2(m - j))!$

那么我们合并一下整个式子，就是：$f(n, k) = \binom{n}{k} ^ 2 k ! 2 ^ k g(n - k) = \binom{n}{k} ^ 2 k ! 2 ^ k \sum_{j = 0} ^ {n - k}(-1) ^ j \binom{n - k}{j} ^ 2 j! 2 ^ j (2(n - k - j))!$

这个式子我们是可以直接求的，于是就完成了。

接下来进入正题，我们注意到刚刚的弱化版内的 $f(n, k) = \binom{n}{k} ^ 2 k ! 2 ^ k D(n - k) $，且 $D(n) = \sum_{i = 0} ^ {n} (-1) ^ i\binom{n}{i} ^ 2 i! 2 ^ i (2(n - i))!$，我们考虑对于 $D(n)$ 进行化简.

$\sum_{i = 0} ^ {n}(-1) \binom{n}{i} ^ 2 i! 2 ^ i (2(n - i)) != (n!) ^ 2 \sum_{i = 0} ^ n \frac{(2(n - i))!}{(n - i)! ^ 2} \frac{(-2) ^ i}{i!}$

这里我们就可以直接做卷积了，但是问题在于这个题目要求的复杂度太过苛刻，卷积无法通过此题，我们考虑构造生成函数。

我们设：$F(x) = (n!) ^ 2 \sum_{i = 0} ^ n \frac{(2(n - i))!}{(n - i)! ^ 2} \frac{(-2) ^ i}{i!} x^i,G[n] = \frac{(2n)!}{n!^2},P[n] = \frac{(-2) ^ i}{n !}$。那么，由离散卷积可知：$F(x) = G(x) * P(x)$

接下来，我们只需要分别对于 $G(x)$ 和 $P(x)$ 化简即可。首先，对于 $G(x)$ 来说，我们可以利用**广义二项式定理**，那么什么是广义二项式定理呢？对于任意实数 $\alpha$，都有 $(1 + z) ^ \alpha = \sum_{i = 0} ^ {\infty} \binom{\alpha}{i} z ^ i$，那么说我们就可以化简 $G(x)$ 了：$G(x) = \sum_{i = 0} \frac{(-2x) ^ i}{i!} x ^ i = \sum_{i = 0} \binom{2i}{i}x^i = \frac{1}{\sqrt{1 - 4x}}$对于 $P(x)$ 来说，直接化简：$P(x) = \sum_{i = 0} \frac{(-2x)!}{i!} = e ^ {-2x}$

经过化简，我们可以最终得到：$F(x) = \frac{e ^ {-2x}}{\sqrt{1 - 4x}}$对于这个生成函数，为了得到与自身相关的式子进行递推，我们选择对其求导。$F'(x) = \frac{8x * e ^ {-2x}}{(1 - 4x) ^ \frac{3}{2}} = \frac{8x}{1 - 4x} F(x)$整理一下：$F'(x) = 4xF'(x) + 8xF(x)$。提取 $[x ^ n]$ 的系数：$F'[n] = 4xF'[n - 1] + 8xF[n - 1]$。稍施小计，我们可以直接得到关于 $F[n]$ 的递推式：$(n + 1)F[n + 1] = 4nF[n] + 8F[n - 1]$

你可能以为万事大吉了，但是问题是我们还有个 $(n!) ^ 2$ 的系数在最开始被我们提出去了，我们要把这玩意弄回来，带入 $F[n] = \frac{D(n)}{n!} ^ 2$：$(n + 1)\frac{D[n + 1]}{(n + 1)!} = 4n \frac{D[n]}{n!^2} + 8 \frac{D[n - 1]}{(n - 1)! ^ 2}$我们就可以得到关于 $D[n]$ 的递推式：$D[n + 1] = 4n(n + 1)D[n] + 8n ^ 2(n + 1)D[n - 1]$

直接 $O(n)$ 递推即可。

代码

#include<iostream>
using namespace std;

#define int long long
const int MOD = 998244353;
const int MAXN = 2e3 + 5;

int C[MAXN][MAXN];
int fac[MAXN];
int g[MAXN], pow2[MAXN];

void init(){
	C[0][0] = 1;
	for(int i = 1;i < MAXN;i ++){
		C[i][0] = C[i][i] = 1;
		for(int j = 1;j < i;j ++){
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
		}
	}
	fac[0] = 1;
	for(int i = 1;i < MAXN;i ++){
		fac[i] = (fac[i - 1] * i) % MOD;
	}
	pow2[0] = 1;
	for(int i = 1;i < MAXN;i ++){
		pow2[i] = pow2[i - 1] * 2 % MOD;
	}
	for(int m = 0;m <= 1000;m ++){
		g[m] = 0;
		for(int j = 0;j <= m;j ++){
			int a = (j % 2 == 0) ? 1 : MOD - 1;
			int res = C[m][j] * C[m][j] % MOD;
			res = (res * fac[j]) % MOD;
			res = (res * pow2[j]) % MOD;
			res = (res * fac[2 * (m - j)]) % MOD;
			res = (res * a) % MOD;
			g[m] = (g[m] + res) % MOD;
		}
 	}
	return;
}

int f(int n, int k){
	int res = (C[n][k] * C[n][k]) % MOD;
	res = (res * fac[k]) % MOD;
	res = (res * pow2[k]) % MOD;
	res = (res * g[n - k]) % MOD;
	return res;
}

int T, n, k;

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	init();

	cin >> T;

	while(T --){
		cin >> n;
		for(int i = 0;i <= n;i ++){
			cout << f(n, i) << '\n';
		}
	}

	return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19617614

大意

每一个小朋友在得到自己喜欢的饮料和食物的时候，就实现了其愿望，问最多能实现多少奶牛的愿望。

思路

首先我们考虑这样的三元关系 $(饮料，小朋友，食物)$，这样的三元关系，如果我们直接在中间连边去跑最大流是否有问题呢？

显然是有问题的，如下图：

这样我们发现个奇怪的问题，一个小朋友对应的喜欢的食物和饮料其实是很多的，但是这样会使得不同的饮料与食物都对一个小朋友产生影响，现在我们需要做的是给一个点上约束，而这种技巧叫做拆点。

我们考虑将每个小朋友拆为 $in$ 和 $out$，在 $in$ 和 $out$ 间连容量为 $1$ 的边，这样我们就可以保证每个小朋友只被算一次，如下图：

在拆完点之后直接跑最大流即可。

代码

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAX_N = 1000;
const int MAX_M = 100000;
struct edge {
    int v, c, next;
} e[MAX_M];
int p[MAX_N], eid;
void init() {
    memset(p, -1, sizeof(p));
    eid = 0;
}
void insert(int u, int v, int c) {
    e[eid].v = v;
    e[eid].next = p[u];
    e[eid].c = c;
    p[u] = eid++;
}
void addedge(int u, int v, int c) {
    insert(u, v, c);
    insert(v, u, 0);
}
int S, T;
int d[MAX_N];
bool bfs() {
    memset(d, -1, sizeof(d));
    queue<int> q;
    q.push(S);
    d[S] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = p[u]; i != -1; i = e[i].next) {
            int v = e[i].v;
            if (e[i].c > 0 && d[v] == -1) {
                q.push(v);
                d[v] = d[u] + 1;
            }
        }
    }
    return (d[T] != -1);
}
int dfs(int u, int flow) {
    if (u == T) {
        return flow;
    }
    int res = 0;
    for (int i = p[u]; i != -1; i = e[i].next) {
        int v = e[i].v;
        if (e[i].c > 0 && d[u] + 1 == d[v]) {
            int tmp = dfs(v, min(flow, e[i].c));
            flow -= tmp;
            e[i].c -= tmp;
            res += tmp;
            e[i ^ 1].c += tmp;
            if (flow == 0) {
                break;
            }
        }
    }
    if (res == 0) {
        d[u] = -1;
    }
    return res;
}
int Dinic() {
    int res = 0;
    while (bfs()) {
        res += dfs(S, INF);
    }
    return res;
}
int main() {
    init();
    int n, m, k;
    cin >> n >> m >> k;
    for(int i = 1;i <= n;i ++){
        addedge(m + i, m + n + i, 1);
        int a, b; cin >> a >> b;
        for(int j = 0;j < a;j ++){
            int x; cin >> x;
            addedge(x, m + i, 1);
        }
        for(int j = 0;j < b;j ++){
            int x; cin >> x;
            addedge(m + n + i, m + 2 * n + x, 1);
        }
    }
    S = 0; T = m + 2 * n + k + 1;
    for(int i = 1;i <= m;i ++){
        addedge(S, i, 1);
    }
    for(int i = 1;i <= k;i ++){
        addedge(m + 2 * n + i, T, 1);
    }
    cout << Dinic() << endl;
    return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19617931

大意

$N$ 个顾客，$M$ 个技术人员，不同的技术人员对不同的车的修理时间是不同的，那么求顾客们的最短等待时间。

思路

我们发现，对于这个题来说，很像排队接水(~~不是~~)。

考虑每个技术人员的时候，我们发现如下规律，一个技术人员对答案所作出的贡献是：

$最后一个顾客时间 \times 1 + 倒数第二个顾客时间 \times 2  ... 倒数第 k 个顾客时间 \times k$

我们发现，每个技术人员在不同时刻的状态是不一样的，对答案所做出的贡献也是，不一样的，但是每个状态下的技术人员只能给一个人修车，但是顾客可以自行选择某个状态下的某个技术人员。

这个问题我们可以用网络流来解决，我们对于每个技术人员，将其拆分为 $n$ 个状态，对于正在给倒数第 $k$ 个顾客修车的师傅 $i$ 对顾客 $j$ 连一条容量为 $1$，费用为 $t_{i, j} \times k$，对于源点向每个技术人员的每个状态连容量为 $1$，花费为 $0$ 的边，对于每个顾客都向汇点 $T$ 去连上容量为 $1$，花费为 $0$ 的边。

这样跑出的最小费用最大流就一定会自己最优的选择出最短的排队修车的时间。

代码

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

const int MAXN = 1005;
const int MAXM = 100005;
struct node{
    int u, v, nxt, c, w;
}e[MAXM * 2];

int S, T;
int tot, h[MAXN], d[MAXN], pre[MAXN];
bool vis[MAXN];

void init(){
    tot = 0;
    memset(h, -1, sizeof(h));
}

void add(int u, int v, int c, int w){
    e[tot] = {u, v, h[u], c, w};
    h[u] = tot ++;
    e[tot] = {v, u, h[v], 0, -w};
    h[v] = tot ++;
}

bool spfa(){
    memset(vis, 0, sizeof(vis));
    memset(d, 0x3f, sizeof(d));
    memset(pre, -1, sizeof(pre));
    queue<int> q;
    q.push(S);
    d[S] = 0;
    vis[S] = true;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i = h[u];~i;i = e[i].nxt){
            int v = e[i].v;
            if(e[i].c > 0){
                if(d[v] > d[u] + e[i].w){
                    d[v] = d[u] + e[i].w;
                    pre[v] = i;
                    if(!vis[v]){
                        q.push(v);
                        vis[v] = true;
                    }
                }
            }
        }
    }
    return (d[T] != 0x3f3f3f3f);
}

int EK(){
    int res = 0;
    while(spfa()){
        int Min = 1e9;
        for(int i = T;i != S;i = e[pre[i]].u){
            Min = min(Min, e[pre[i]].c);
        }
        for(int i = T;i != S;i = e[pre[i]].u){
            e[pre[i]].c -= Min;
            e[pre[i] ^ 1].c += Min;
            res += e[pre[i]].w * Min;
        }
    }
    return res;
}

int m, n;

int main(){
    // freopen("repair.in", "r", stdin);
    // freopen("repair.out", "w", stdout);
    cin >> m >> n;
    init();

    S = 0, T = n + m * n + 1;

    for(int i = 1;i <= n;i ++){
        add(S, i, 1, 0);
    }

    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            int t_cost;
            cin >> t_cost;
            for(int k = 1;k <= n;k ++){
                int pos = n + (j - 1) * n + k;
                add(i, pos, 1, k * t_cost);
            }
        }
    }

    for(int j = 1;j <= m;j ++){
        for(int k = 1;k <= n;k ++){
            add(n + (j - 1) * n + k, T, 1, 0);
        }
    }

    int ans = EK();
    printf("%.2f\n", (double)ans / n);

    return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19619769

大意

一个餐厅在相继的 $N$ 天里，每天需用的餐巾数不尽相同。假设第 $i$ 天需要 $r_i$ 块餐巾（$i = 1, 2, \dots, N$）。餐厅可以购买新的餐巾，每块餐巾的费用为 $p$ 分；或者把旧餐巾送到快洗部，洗一块需 $m$ 天，其费用为 $f$ 分；或者送到慢洗部，洗一块需 $n$ 天（$n \gt m$），其费用为 $s$ 分（$s \lt f$）。每天结束时，餐厅必须决定将多少块脏的餐巾送到快洗部，多少块餐巾送到慢洗部，以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和，要满足当天的需求量。

思路

一道很好的费用流题目，我们做一下考虑。

最终，由于每天都需要 $r_i$ 块餐巾布，那么最终我们的最大流一定是 $\sum r_i$，但是由于题目中的条件导致我们一定能求出最大流为 $\sum r_i$，主要的问题是费用最小，考虑如何建模。

首先每天我们首先要要求在这天开始的时候，有 $r_i$ 块新餐巾，而经过使用，这些餐巾在这天结束的时候会变成脏餐巾，那么我们考虑拆点，将一天分为 $in$ 和 $out$，$in$ 表示每天开始的时候，$out$ 表示每天结束的时候。

首先，我们需要向 $i_{out}$ 注入脏餐巾，我们建立源点 $S$，用来产生脏餐巾，容量为 $r_i$，花费为 $0$，其次我们建立汇点 $T$ 用来接收干净的餐巾，那么由 $i_{in}$ 向 $T$ 连容量为 $r_i$ 花费为 $0$ 的边。这样一来，如果最大流跑不满，就说明不可行。

接下来考虑题目中的约束，为了使得每天的 $i_{out} \to T$ 的流量流满，其实就是满足题目中的每天买餐巾的需求，我们可以从源点 $S$ 向每个 $i_{in}$ 连容量为 $\infty$，花费为 $p$ 的边。

接下来是洗衣服的约束，我们只需要每天的 $i_{out} \to {(i + m)}_{in}$ 容量为 $\infty$，花费为 $f$ 的边，$i_{out} \to {(i + n)}_{in}$ 容量为 $\infty$，花费为 $s$ 的边。

这样一来，直接跑最小费用最大流即可。

代码

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

const int MAXN = 4005;
const int MAXM = 20005;
struct node{
    int u, v, nxt, c, w;
}e[MAXM * 2];

int S, T;
int tot, h[MAXN], d[MAXN], pre[MAXN];
bool vis[MAXN];

void init(){
    tot = 0;
    memset(h, -1, sizeof(h));
}

void add(int u, int v, int c, int w){
    e[tot] = {u, v, h[u], c, w};
    h[u] = tot ++;
    e[tot] = {v, u, h[v], 0, -w};
    h[v] = tot ++;
}

bool spfa(){
    memset(vis, 0, sizeof(vis));
    memset(d, 0x3f, sizeof(d));
    memset(pre, -1, sizeof(pre));
    queue<int> q;
    q.push(S);
    d[S] = 0;
    vis[S] = true;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i = h[u];~i;i = e[i].nxt){
            int v = e[i].v;
            if(e[i].c > 0){
                if(d[v] > d[u] + e[i].w){
                    d[v] = d[u] + e[i].w;
                    pre[v] = i;
                    if(!vis[v]){
                        q.push(v);
                        vis[v] = true;
                    }
                }
            }
        }
    }
    return (d[T] != 0x3f3f3f3f);
}

long long EK(){
    long long res = 0;
    while(spfa()){
        long long Min = 1e9;
        for(int i = T;i != S;i = e[pre[i]].u){
            Min = min(Min, (long long)e[pre[i]].c);
        }
        for(int i = T;i != S;i = e[pre[i]].u){
            e[pre[i]].c -= Min;
            e[pre[i] ^ 1].c += Min;
            res += e[pre[i]].w * Min;
        }
    }
    return res;
}

int N;
int a[MAXN];
int p, m, f, n, s;


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
//    freopen("repair.in", "r", stdin);
//    freopen("repair.out", "w", stdout);
    cin >> N;
    init();
    for(int i = 1;i <= N;i ++){
    	cin >> a[i];
	}
	S = 0, T = 2 * N + 1;
	cin >> p >> m >> f >> n >> s;
	for(int i = 1;i <= N;i ++){
		add(S, i + N, a[i], 0);
		add(S, i, 1e9, p);
		add(i, T, a[i], 0);
		if(i + 1 <= N){
			add(i + N, (i + 1) + N, 1e9, 0);
		}
		if(i + m <= N){
			add(i + N, (i + m), 1e9, f);
		}
		if(i + n <= N){
			add(i + N, (i + n), 1e9, s);
		}
	}
	cout << EK() << endl;
    return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19623719

大意

树上修改，路径和，路径最值，路径取反。

思路

基础树剖 + 线段树维护。

代码

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

#define lc u << 1
#define rc u << 1 | 1
const int MAXN = 2 * 1e5 + 5;
const int INF = 1e9;
int sz[MAXN], top[MAXN], dep[MAXN];
int fa[MAXN], son[MAXN], dfn[MAXN], stk;
int nw[MAXN], n, val[MAXN];
int u_in[MAXN], v_in[MAXN], w_in[MAXN];

struct node{
	int to, nxt, len;
}e[MAXN << 1];
int tot = 0, h[MAXN];

void add(int u, int v, int w){
	e[++ tot] = {v, h[u], w};
	h[u] = tot;
}

void dfs1(int u, int f, int w){
	sz[u] = 1;
	fa[u] = f;
	dep[u] = dep[f] + 1;
	val[u] = w;
	son[u] = 0;
	for(int i = h[u];i;i = e[i].nxt){
		int v = e[i].to;
		if(v == f) continue;
		dfs1(v, u, e[i].len);
		sz[u] += sz[v];
		if(sz[v] > sz[son[u]]){
			son[u] = v;
		}
	}
}

void dfs2(int u, int tp){
	top[u] = tp;
	dfn[u] = ++ stk;
	nw[stk] = val[u];
	if(!son[u]) return;
	dfs2(son[u], tp);
	for(int i = h[u];i;i = e[i].nxt){
		int v = e[i].to;
		if(v == fa[u] || v == son[u]){
			continue;
		}
		dfs2(v, v);
	}
}

int sum[MAXN << 2];
int mx[MAXN << 2], mn[MAXN << 2];
bool lz[MAXN << 2];

void pushup(int u){
	sum[u] = sum[lc] + sum[rc];
	mx[u] = max(mx[lc], mx[rc]);
	mn[u] = min(mn[lc], mn[rc]);
}

void apply(int u){
	sum[u] = -sum[u];
	swap(mx[u], mn[u]);
	mx[u] = -mx[u];
	mn[u] = -mn[u];
	lz[u] = !lz[u];
}

void pushdown(int u){
	if(lz[u]){
		apply(lc);
		apply(rc);
		lz[u] = 0;
	}
}
void build(int u, int l, int r){
	if(l == r){
		if(l == 1){
			sum[u] = 0, mx[u] = -INF, mn[u] = INF;
		}
		else{
			sum[u] = mx[u] = mn[u] = nw[l];
		}
		return;
	}
	int mid = (l + r) >> 1;
	build(lc, l, mid);
	build(rc, mid + 1, r);
	pushup(u);
}

void p_modify(int u, int l, int r, int x, int v){
	if(l == r){
		sum[u] = mx[u] = mn[u] = v;
		lz[u] = false;
		return;
	}
	pushdown(u);
	int mid = (l + r) >> 1;
	if(x <= mid){
		p_modify(lc, l, mid, x, v);
	}
	else{
		p_modify(rc, mid + 1, r, x, v);
	}
	pushup(u);
}

void l_modify(int u, int l, int r, int L, int R){
	if(L <= l && r <= R){
		apply(u);
		return;
	}
	pushdown(u);
	int mid = (l + r) >> 1;
	if(L <= mid) l_modify(lc, l, mid, L, R);
	if(R > mid) l_modify(rc, mid + 1, r, L, R);
	pushup(u);
}

int ask_sum(int u, int l, int r, int L, int R){
	if(L <= l && r <= R){
		return sum[u];
	}
	pushdown(u);
	int ans = 0;
	int mid = (l + r) >> 1;
	if(L <= mid){
		ans += ask_sum(lc, l, mid, L, R);
	}
	if(R > mid){
		ans += ask_sum(rc, mid + 1, r, L, R);
	}
	return ans;
}

int ask_max(int u, int l, int r, int L, int R){
	if(L <= l && r <= R){
		return mx[u];
	}
	pushdown(u);
	int ans = -INF;
	int mid = (l + r) >> 1;
	if(L <= mid){
		ans = max(ask_max(lc, l, mid, L, R), ans);
	}
	if(R > mid){
		ans = max(ans, ask_max(rc, mid + 1, r, L, R));
	}
	return ans;
}

int ask_min(int u, int l, int r, int L, int R){
	if(L <= l && r <= R){
		return mn[u];
	}
	pushdown(u);
	int ans = INF;
	int mid = (l + r) >> 1;
	if(L <= mid){
		ans = min(ans, ask_min(lc, l, mid, L, R));
	}
	if(R > mid){
		ans = min(ans, ask_min(rc, mid + 1, r, L, R));
	}
	return ans;
}

void path_modify(int u, int v){
	while(top[u] != top[v]){
		if(dep[top[u]] < dep[top[v]]){
			swap(u, v);
		}
		l_modify(1, 1, n, dfn[top[u]], dfn[u]);
		u = fa[top[u]];
	}
	if(u == v) return;
	if(dep[u] > dep[v]) swap(u, v);
	l_modify(1, 1, n, dfn[u] + 1, dfn[v]);
}

int path_sum(int u, int v){
	int ans = 0;
	while(top[u] != top[v]){
		if(dep[top[u]] < dep[top[v]]){
			swap(u, v);
		}
		ans += ask_sum(1, 1, n, dfn[top[u]], dfn[u]);
		u = fa[top[u]];
	}
	if(u == v) return ans;
	if(dep[u] > dep[v]){
		swap(u, v);
	}
	ans += ask_sum(1, 1, n, dfn[u] + 1, dfn[v]);
	return ans;
}

int path_max(int u, int v){
	int ans = -INF;
	while(top[u] != top[v]){
		if(dep[top[u]] < dep[top[v]]){
			swap(u, v);
		}
		ans = max(ans, ask_max(1, 1, n, dfn[top[u]], dfn[u]));
		u = fa[top[u]];
	}
	if(u == v) return ans;
	if(dep[u] > dep[v]){
		swap(u, v);
	}
	ans = max(ans, ask_max(1, 1, n, dfn[u] + 1, dfn[v]));
	return ans;
}

int path_min(int u, int v){
	int ans = INF;
	while(top[u] != top[v]){
		if(dep[top[u]] < dep[top[v]]){
			swap(u, v);
		}
		ans = min(ans, ask_min(1, 1, n, dfn[top[u]], dfn[u]));
		u = fa[top[u]];
	}
	if(u == v) return ans;
	if(dep[u] > dep[v]){
		swap(u, v);
	}
	ans = min(ans, ask_min(1, 1, n, dfn[u] + 1, dfn[v]));
	return ans;
}

int main(){
    freopen("travel.in", "r", stdin);
    freopen("travel.out", "w", stdout);
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i = 1; i < n; i++){
		cin >> u_in[i] >> v_in[i] >> w_in[i];
		u_in[i]++; v_in[i]++;
		add(u_in[i], v_in[i], w_in[i]);
		add(v_in[i], u_in[i], w_in[i]);
	}
	dfs1(1, 0, 0);
	dfs2(1, 1);
	build(1, 1, n);
	int m; cin >> m;
	while(m--){
		string op; cin >> op;
		int x, y; cin >> x >> y;
		if(op == "C"){
			int target = dep[u_in[x]] > dep[v_in[x]] ? u_in[x] : v_in[x];
			p_modify(1, 1, n, dfn[target], y);
		} else {
			x++; y++;
			if(op == "N") path_modify(x, y);
			else if(op == "SUM") cout << path_sum(x, y) << "\n";
			else if(op == "MAX") cout << path_max(x, y) << "\n";
			else if(op == "MIN") cout << path_min(x, y) << "\n";
		}
	}
	return 0;
}