时间安排

• $7:50$ 开题
• $7:50-8:10$ 先把三道题都看了一遍 。$T1$ 应该是个点分治，然后用 $ds$ 维护信息。 $T2$ 有点神秘。 $T3$ 好像是山东省集的例题，但是当时就没有听懂。
• $8:10-9:20$ 冲 $T1$。首先要求路径答案，所以可以点分治。然后需要求起点到重心从 $1$ 开始最大能延伸到哪，以及重心到终点以某个数字为结尾最小可以连续到哪。然后发现这个可以写一个主席树每个点继承它的父亲的答案。查询只需要支持单点查和线段树二分即可。复杂度双 $log$。然后果断开冲。连写带调用了 $45min$。
• $9:20-10:00$ 看 $T2$，中间的具体思考过程忘了，只是记得以为自己会了结果发现题看错导致假了。
• $10:00-10:50$ 重新思考 $T2$，推出了一些结论。然后得到了一个 $m^{2}n$ 的做法，可以拿到 $44pts$。写了一发，发现过不了，全都 $T$了。以为就是会被卡，过了一会儿测了一下大数据发现RE了，然后调了一下过了 $44pts$。
• $10:50-11:00$ 本想着去看看 $T3$，但是看完一眼并没有什么很好的思路，只会 $10pts$ 的暴力。而且感觉 $T2$ 还可以再拿一点分，就又回去看 $T2$。
• $11:00-11:40$ 一直再想 $T2$ 如何优化。最后还剩 $30min$ 意识到只需要求出每个点与关键点相互连通的最早时间，然后对答案数组差分一下就行。求时间只需要跑最短路即可。看一眼复杂度好像是 $O(nm{\log }_{2}n)$ 的，但是我写了一个 $spfa$ 上去了，交上去有 $80pts$。
• $11：45-12：00$ 没啥时间了，感觉 $T2$ 就算改成 $O(nm{\log }_{2}n)$ 也过不去，就去写 $T3$ $10pts$ 了。最后也是喜提没叫上。

得分：100 + 80 + 0
rk2
赛后才知道三道题都是之前省选的原题。

题解

T1.[省选联考 2021 A/B 卷] 宝石

原题：
[省选联考 2021 A/B 卷] 宝石

题意：
给定一棵 $n$ 个点的树，每个点上有一个数 $w_i$，满足 $w_i\in [1,m]$。你有一个收容器，可以收集至多 $c$ 个数，并且必须按照 $P_1,P_2,...,P_c$ 的顺序收集，其中 $P_i$ 互不相同，每种数最多被收集一次。现在有 $q$ 次询问，每次询问给你一条有向路径 $s\to t$，问依次最多可以收集多少数字。

数据规模：
$1\le n,q\le 2\times 10^5$， $1\le c\le m\le 5\times 10^4$。

分析：
既然是处理路径询问，我们考虑 点分治。
先将所有数 $w_i$ 换成它在 $P_i$ 数组中的排名。如果没有这种数就赋值成 $0$。
那么我们要求的就是一条有向路径上从 $1$ 开始的最长 $1,2,...$ 子序列的长度。
考虑怎么求一条经过重心的路径的答案：
设 $f_{i,x}$ 表示 $i$ 号点到重心的路径上以 $x$ 数字为开头每次递增 $1$ 的子序列的结尾最大能到几。
$g_{i,x}$ 表示重心到 $i$ 号点的路径上以 $x$ 数字为结尾每次递增 $1$ 的子序列的开头最小能到几。
那么一条路径就是 $\underset{x}{\max }(x)(g_{t,x}\le f_{s,1})$。
考虑怎么维护 $f$ 和 $g$。发现从重心开始往下递归的过程中 $f_x$ 可以由它的父亲 $fa$ 的 $f_{fa}$ 继承过来。只需要单点修改一个 $f_{x,w_x}$ 即可。那么这个可以用主席树维护。
$g$ 的维护方式同理。
那么对于线段树而言只需要维护区间最小值，能够支持单点查询。
查询答案时只需要单点查 $f_{s,1}$，然后在 $g_t$ 的线段树上二分即可。
复杂度 $O(n\times {\log }_{2}n\times {\log }_{2}m)$。
CODE：

// 点分治 + 主席树 
#include<bits/stdc++.h>
#define pb emplace_back
#define MP make_pair
using namespace std;
typedef pair< int, int > PII;
const int N = 2e5 + 10;
int n, m, q, c, w[N];
int p[N], idx[N];
int ans[N];
vector< PII > qry[N];
vector< int > E[N];
int root, Maxn[N], sz[N], all;
bool vis[N]; // 每个点是否被标记过 
void get_root(int x, int fa) {
	sz[x] = 1; Maxn[x] = 0;
	for(auto v : E[x]) {
		if(v == fa || vis[v]) continue;
		get_root(v, x);
		Maxn[x] = max(Maxn[x], sz[v]);
		sz[x] += sz[v]; 
	}
	Maxn[x] = max(Maxn[x], all - sz[x]);
	if(Maxn[x] < Maxn[root]) root = x;
}
void get_sz(int x, int fa) {
	sz[x] = 1;
	for(auto v : E[x]) {
		if(v == fa || vis[v]) continue;
		get_sz(v, x);
		sz[x] += sz[v];
	}
}
int tot, Root[N]; // 每个点的根 
int bok[N]; // 每个点所属子树的标记 
struct SegmentTree {
	int ls, rs, mx, mn;
	#define ls(x) t[x].ls
	#define rs(x) t[x].rs
	#define mx(x) t[x].mx
	#define mn(x) t[x].mn
}t[N * 20];
int build() {
	tot ++;
	ls(tot) = rs(tot) = mx(tot) = 0;
	mn(tot) = n + 10;
	return tot;
}
void update(int p) {
	int lmx = (ls(p) ? mx(ls(p)) : 0), rmx = (rs(p) ? mx(rs(p)) : 0);
	int lmn = (ls(p) ? mn(ls(p)) : n + 10), rmn = (rs(p) ? mn(rs(p)) : n + 10);
	mx(p) = max(lmx, rmx);
	mn(p) = min(lmn, rmn);
}
int ask_max(int p, int lp, int rp, int pos) {
	if(lp == rp) return mx(p);
	int mid = (lp + rp >> 1);
	if(pos <= mid) return ask_max(ls(p), lp, mid, pos);
	else return ask_max(rs(p), mid + 1, rp, pos);
}
int ask_min(int p, int lp, int rp, int pos) {
	if(lp == rp) return mn(p);
	int mid = (lp + rp >> 1);
	if(pos <= mid) return ask_min(ls(p), lp, mid, pos);
	else return ask_min(rs(p), mid + 1, rp, pos);
}
int query(int p, int lp, int rp, int k) {
	if(mn(p) > k) return 0;
	if(lp == rp) return mn(p) <= k ? lp : 0;
	int mid = (lp + rp >> 1);
	if(rs(p) && mn(rs(p)) <= k) return query(rs(p), mid + 1, rp, k);
	else return query(ls(p), lp, mid, k);
}
int ins(int fa, int p, int lp, int rp, int c) { // 插入一个权值为 c 的点 
	int tp = build(); t[tp] = t[p];
	if(lp == rp) {
		if(c == 0) return tp;
		else {
			int v = ask_max(Root[fa], 0, n + 1, c + 1);
			if(v == 0) mx(tp) = c;
			else mx(tp) = v;
			v = ask_min(Root[fa], 0, n + 1, c - 1);
			if(v == 0) mn(tp) = c;
			else mn(tp) = v;
			return tp;
		}
	}
	int mid = (lp + rp >> 1);
	if(c <= mid) ls(tp) = ins(fa, ls(tp), lp, mid, c);
	else rs(tp) = ins(fa, rs(tp), mid + 1, rp, c);
	update(tp);
	return tp;
}
void dfs(int x, int fa, int bel) {
	bok[x] = bel;
	Root[x] = ins(fa, Root[fa], 0, n + 1, w[x]);
	for(auto v : E[x]) {
		if(v == fa || vis[v]) continue;
		dfs(v, x, bel);
	}
}
void Q(int x) {
	for(auto v : qry[x]) { // 枚举所有以 x 为 起点的询问 
		int id = v.first, u = v.second;
		if(bok[x] == bok[u] || ans[id] != -1) continue;
		int p = ask_max(Root[x], 0, n + 1, 1); // 查询 1 处的答案 
		int q = query(Root[u], 0, n + 1, p + 1); // 求最小值小于等于 p + 1 的 最大值 
		ans[id] = max(q, p);
	}
}
void dfs_ans(int x, int fa) {
	Q(x);
	for(auto v : E[x]) {
		if(v == fa || vis[v]) continue;
		dfs_ans(v, x);
	}
}
void solve(int rt) { // 处理所有经过 rt 的路径   每次用完都要清空主席树 
    vis[rt] = 1; tot = 0;
    Root[root] = ins(0, Root[0], 0, n + 1, w[rt]);
    bok[rt] = rt;
	for(auto v : E[rt]) {
		if(!vis[v]) dfs(v, rt, v);
	}
	Q(rt);
	for(auto v : E[rt]) {
		if(!vis[v]) dfs_ans(v, rt);
	}
	for(auto v : E[rt]) {
		if(vis[v]) continue;
		root = 0; all = sz[v];
		get_root(v, 0);
		get_sz(root, 0);
		solve(root);
	}
}
int main() {
	freopen("gem.in", "r", stdin);
	freopen("gem.out", "w", stdout);
	scanf("%d%d%d", &n, &m, &c);
	for(int i = 1; i <= c; i ++ ) {
		scanf("%d", &p[i]);
		idx[p[i]] = i;
	}
	for(int i = 1; i <= n; i ++ ) {
		scanf("%d", &w[i]);
		w[i] = idx[w[i]];
	}
	for(int i = 1; i < n; i ++ ) {
		int u, v; scanf("%d%d", &u, &v);
		E[u].pb(v); E[v].pb(u);
	}
	scanf("%d", &q);
	for(int i = 1; i <= q; i ++ ) {
		int s, t; scanf("%d%d", &s, &t);
		qry[s].pb(MP(i, t));
	}
	memset(ans, -1, sizeof ans);
	Maxn[0] = n + 1; all = n;
	get_root(1, 0);
	get_sz(root, 0);
	solve(root);
	for(int i = 1; i <= q; i ++ ) printf("%d\n", ans[i]);
	return 0;
}

T2. [省选联考 2021 A/B 卷] 图函数

感觉是一道非常有技巧的题。

原题：
[省选联考 2021 A/B 卷] 图函数

题意：
对于一张 $n$ 个点 $m$ 条边的有向图 $G$（顶点从 $1\sim n$ 编号），定义函数 $f(u,G)$：

1. 初始化返回值 $cnt=0$，图 $G^{\prime }=G$。
2. 从 $1$ 至 $n$ 按顺序枚举顶点 $v$，如果当前的图 $G^{\prime }$ 中，从 $u$ 到 $v$ 与从 $v$ 到 $u$ 的路径都存在，则将 $cnt+1$，并在图 $G^{\prime }$ 中删去顶点 $v$ 以及与它相关的边。
3. 第 $2$ 步结束后，返回值 $cnt$ 即为函数值。

现在给定一张有向图 $G$，请你求出 $h(G)=f(1,G)+f(2,G)+\cdots +f(n,G)$ 的值。

更进一步地，记删除（按输入顺序给出的）第 $1$ 到 $i$ 条边后的图为 $G_i$（$1\le i\le m$），请你求出所有 $h(G_i)$ 的值。

数据规模：

$2\le n\le {10}^3$，$1\le m\le 2\times {10}^5$，$1\le x_i,y_i\le n$。

分析：
首先对于一张确定的图 $G$，我们将答案拆成所有点对 $(u,v)(u\le v)$ 的贡献。
含义是 $f(v,G)$ 时 $u$ 会产生 $1$ 的贡献。
那么需要满足 $u\le v$。否则 $v$ 会比 $u$ 先删除因此枚举到 $u$ 时一定删不了。

考虑 $(u,v)$ 会产生贡献的条件：

相当于考虑过 $1\sim u-1$ 这些点的删除情况后 $u$ 和 $v$ 仍然在一个强连通分量里。

在最开始一个点还没有删的条件下，图就会形成若干个强连通分量。那么 $1\sim u-1$ 中 只可能 删除那些开始就和 $v$ 在同一个强连通分量里的点。
但是换一个角度想：

对于一个点 $i\in [1,u-1]$，如果此时它和 $v$ 不在一个强连通分量里，我们把它删掉不会影响后边本来能删的点，也不会影响最后 $u$ 是否能删。
如果 $i$ 可以被删掉，那么我们就把它删掉。

因此求 $f(v,G)$ 时 $u$ 能被删掉的充要条件是 删掉 $1\sim u-1$号点后 $u$ 依然和 $v$ 在一个强连通分量里。

我们称删掉了 $1\sim i$ 号点后 为 $i$ 时刻。如果一个点也没删为 $0$ 时刻。
那么对于一张图 $G$ 而言： $\sum _{u}f(u,G)$ 的值为 $i:0\sim n-1$ 时刻 $i+1$ 所在的强连通分量的大小之和。
这样我们可以得到一个 $O(m^2\times n)$ 的做法：枚举每一张图，暴力对每一个时刻跑一遍 $tarjan$。

下面是更优的做法：

更形式化的描述 $(u,v)$ 对图 $G$ 产生贡献的条件：相当于需要存在一条 只经过 $\ge u$ 的点 从$u$ 到 $v$ 的路径，和一条从 $v$ 到 $u$ 的路径。
考虑到从前往后删边图的连通性逐渐减弱。因此 $(u,v)$ 产生贡献的图是一个前缀。
如果我们将边的 编号 看作 边权，一条路径的 长度 定义为 路径上所有边权的最小值。
设 $di{s}_{u,v}$ 表示 只经过 $\ge \min (u,v)$ 的点， $u\to v$ 的最长路，那么 $0\sim \min (di{s}_{u,v},di{s}_{v,u})-1$ 就是 $(u,v)$ 能产生贡献的前缀。

如果我们能求出来 $di{s}_{u,v}$，那么只需要枚举两个点差分一下就可以求出每张图的答案。问题在于怎么求 $dis$。

第一种做法是 从大到小 加点跑 $floyd$。但是这个需要卡常(也能过)，具体写法见代码。
CODE：

#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
struct IO{
    static const int S=1<<21;
    char buf[S],*p1,*p2;int st[105],Top;
    ~IO(){clear();}
    inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
    inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}
    inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
    inline IO&operator >> (char&x){while(x=gc(),x==' '||x=='\n'||x=='\r');return *this;}
    template<typename T>inline IO&operator >> (T&x){
        x=0;bool f=0;char ch=gc();
       while(!isdigit(ch)){if(ch=='-') f^=1;ch=gc();}
        while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=gc();
        f?x=-x:0;return *this;
    }
    inline IO&operator << (const char c){pc(c);return *this;}
    template<typename T>inline IO&operator << (T x){
        if(x<0) pc('-'),x=-x;
        do{st[++st[0]]=x%10,x/=10;}while(x);
        while(st[0]) pc('0'+st[st[0]--]);return *this;
    }
}fin,fout;
const int N = 1e3 + 10;
const int M = 2e5 + 10;
int n, m;
int f[N][N], ans[M];
int main() {
	fin >> n >> m;
	for(int i = 1; i <= m; i ++ ) {
		int u, v;
		fin >> u >> v;
		f[u][v] = max(f[u][v], i);
	}
    for(int i = 1; i <= n; i ++ ) f[i][i] = m + 1;
    for(int k = n; k >= 1; k -- ) { // 从大到小枚举中间点 
     	for(int i = 1; i <= n; i ++ ) {
     		if(!f[i][k]) continue; // 第一个剪枝
     		int lim = (i < k ? n : k - 1); // 第二个剪枝，相当于不能用 k 去更新 (i, j) 都大于 k 的点对。
     		for(int j = 1; j <= lim; j ++ ) 
			    f[i][j] = max(f[i][j], min(f[i][k], f[k][j]));
		}
	}
    for(int i = 1; i <= n; i ++ ) {
    	for(int j = i; j <= n; j ++ ) {
    	    ans[0] ++, ans[min(f[i][j], f[j][i])] --;
		}
	}
	for(int i = 0; i <= m; i ++ ) 
		if(i) ans[i] += ans[i - 1];
	for(int i = 0; i <= m; i ++ ) fout << ans[i], fout.pc(' ');
	return 0;
}

第二种做法：
考虑枚举一个 $u$，然后求出所有 $di{s}_{u,v}(u\le v)$， $di{s}_{v,u}$ 只需要在反图上跑一遍即可。
然后按照边权从大到小插入每一条边，那么问题就变成了给你一张图和一个起点 $s$，依次插入一条有向边，要求出 最早的时刻 $s$ 能到 $v$。
这个问题感觉挺经典的？？做法是：
假设我们插入了有向边 $(x,y)$。
如果当前 $x,y$ 都可达，那么这条边没用，直接跳过。
如果 $x$ 可达 $y$ 不可达，那么我们将 $y$ 标记成可达然后以 $y$ 为起点跑 $bfs$。
如果 $x$ 不可达并且 $y$ 不可达，那么这条边只有在 $x$ 可达的时候才有用。我们将它加入 $x$ 的出边中。
每条边都只会被经过一次，复杂度 $O(m)$。
这样总复杂度 $O(nm)$。

CODE：

#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
const int M = 2e5 + 10;
const int N = 1e3 + 10;
int n, m, u[M], v[M];
bool bok[N];
namespace Sol2 {
    int ans[M];
    int T[2][N]; //  最小的最大 
    int head[N], tot;
    vector< int > G[N];
	void bfs(int s, int t) { // 相当于按照给定顺序插入一些有向边， 求 s 到每个点的最早时刻
	    for(int i = s; i <= n; i ++ ) T[t][i] = 0;
	    T[t][s] = m + 1;
	    tot = 0; for(int i = s; i <= n; i ++ ) G[i].clear(); // 清空边 
	    for(int i = m; i >= 1; i -- ) {
	    	int uu = u[i], vv = v[i];
	    	if(t == 1) swap(uu, vv);
	    	if(uu < s || vv < s) continue;
	    	if(T[t][vv]) continue;
	    	else if(!T[t][uu]) G[uu].pb(vv);
	    	else {
	    		T[t][vv] = i;
	    		queue< int > q; q.push(vv);
	    		while(!q.empty()) {
	    			int u = q.front(); q.pop();
	    			for(auto vt : G[u]) {
	    				if(T[t][vt]) continue;
	    				else T[t][vt] = i, q.push(vt);
					}
				//	G[u].clear();
				}
			}
		}
	}
    void work(int key) { 
 		bfs(key, 0); // 正反图 
 		bfs(key, 1);
 		for(int i = key; i <= n; i ++ ) { // 枚举每一个点，看它能删除的时刻 
 			int tt = min(T[0][i], T[1][i]);
 			ans[0] ++; ans[tt] --;
		}
	}
	void solve() { 
	    for(int i = n; i >= 1; i -- ) { // 枚举一个时刻对不同的 m 统计答案 
	        work(i); // i 是关键点 
		}
		for(int i = 0; i <= m; i ++ ) {
			if(i) ans[i] += ans[i - 1];
		}
		for(int i = 0; i <= m; i ++ ) cout << ans[i] << ' ';
	}
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= m; i ++ ) cin >> u[i] >> v[i];
    Sol2::solve();
	return 0;
}

T3.[省选联考 2020 A 卷] 树

原题：
[省选联考 2020 A 卷] 树

题意：
给定一棵 $n$ 个结点的有根树 $T$，结点从 $1$ 开始编号，根结点为 $1$ 号结点，每个结点有一个正整数权值 $v_i$。

设 $x$ 号结点的子树内（包含 $x$ 自身）的所有结点编号为 $c_1,c_2,\dots ,c_k$，定义 $x$ 的价值为：

$$val(x)=(v_{c_1}+d(c_1,x))\oplus (v_{c_2}+d(c_2,x))\oplus \cdots \oplus (v_{c_k}+d(c_k,x))$$

其中 $d(x,y)$ 表示树上 $x$ 号结点与 $y$ 号结点间唯一简单路径所包含的边数，$d(x,x)=0$。$\oplus$ 表示异或运算。

请你求出 $\sum _{i=1}^{n}val(i)$ 的结果。

对于 $100\%$ 的数据：$1\le n,v_i\le 525010$，$1\le p_i\le n$。

分析：
感觉很 $tricky$，需要记住。
$val(x)$ 实际上就是一个可重数集所有数的异或和。
发现 $val(x)$ 中的数到求 $x$ 的父亲 $fa$ 时都加 $1$ 了。也就是我们需要一个数据结构支持：集合中的数加 $1$，合并两个数集，求数集中所有数的异或和。
如果没有第一个操作，那么我们可以用 $0/1trie$ 维护，只需要类比线段树合并写一个 $trie$ 树合并即可。
第一个操作也可以用 $0/1trie$ 维护：
正常的 $0/1trie$ 是从 高位到低位 插入每一个数，这样可以方便求异或第$k$ 大等信息。
但是这里我们从 低位到高位 插入每个数，那么一个 $+1$ 操作对 $trie$ 有什么影响呢？
等价于 将第一层$0/1$儿子交换，然后往原来的 $1$ 儿子子树中递归！！！
这个可以模拟进位的过程去理解。
那么这样就可以在 $\log$ 的复杂度内完成一次数集中的数 $+1$。
总复杂度 $O(n\times {\log }_{2}V)$。

CODE：

// 需要支持：
// 将一个数集整体 + 1
// 合并若干数集，求数集里面所有数的异或和
// 使用 trie树，从低位到高位插入。可以支持整体 + 1 
#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long LL;
const int N = 526010; 
int n, v[N];
int root[N], tot, tr[N * 23][2];
int num[N * 23], cnt[N * 23]; // 每个节点当前的异或和  以及经过它的数量 
int val[N], lim = 21;
vector< int > E[N];
int build() {
	tot ++;
	return tot;
}
void update(int p, int bit) {
	num[p] = (num[tr[p][0]] ^ num[tr[p][1]]);
	if(cnt[tr[p][1]] & 1) num[p] |= (1 << bit);
}
void ins(int p, int v, int bit) { // 在 p 节点插入一个值为 v 的数字 
    if(bit == lim + 1) return ;
    if((v >> bit) & 1) { // 右儿子 
     	if(!tr[p][1]) tr[p][1] = build();
     	cnt[tr[p][1]] ++;
     	ins(tr[p][1], v, bit + 1);
	}
	else {
		if(!tr[p][0]) tr[p][0] = build();
		cnt[tr[p][0]] ++;
		ins(tr[p][0], v, bit + 1);
	}
	update(p, bit);
}
int Merge(int p, int q, int bit) {
	if(!p || !q) return p ^ q;
	tr[p][0] = Merge(tr[p][0], tr[q][0], bit + 1);
	tr[p][1] = Merge(tr[p][1], tr[q][1], bit + 1);
	cnt[p] += cnt[q]; 
	update(p, bit);
	return p;
}
void Add(int p, int bit) {
	if(!p) return ;
	if(bit == lim + 1) return ;
	swap(tr[p][0], tr[p][1]); // 交换 
	Add(tr[p][0], bit + 1);
	update(p, bit);
}
void dfs(int x, int fa) {
	root[x] = build();
	ins(root[x], v[x], 0); // 从最低位开始插 
	for(auto v : E[x]) {
		if(v == fa) continue;
		dfs(v, x);
		root[x] = Merge(root[x], root[v], 0);
	}
	val[x] = num[root[x]];
	Add(root[x], 0);
}
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++ ) scanf("%d", &v[i]);
	for(int i = 2; i <= n; i ++ ) {
		int p; scanf("%d", &p);
		E[p].pb(i); E[i].pb(p);
	}
	dfs(1, 0);
	LL res = 0;
	for(int i = 1; i <= n; i ++ ) res += 1LL * val[i];
	printf("%lld\n", res);
	return 0;
}