2020-01-24发表2023-04-15更新杂谈12 分钟读完 (大约1798个字)

除夕闲扯

此页面存在相关页面。关于另一个集合贴，请参见「OI模板梳理」。

此页面中的索引截至 2020.1.24，其中的某些条目可能已经失效。

文化课真好系列。

为了证明 bn 还没入坟，他决定闲的没事瞎bb几句。

所以他对之前的 post 们搞了一个整理，以备~~后人之用~~自己欣赏。

图论

最短路

Dijkstra：OI模板梳理 2.1.1
SPFA: OI模板梳理 2.1.3
Floyd: Floyd本质探究-「题解」灾后重建

树

最小生成树(MST)：OI模板梳理 2.2，变形-CFR599D 0-1 MST
树的重心，树的直径
LCA: 倍增法-最近公共祖先，树链剖分法-树链剖分 3.1
树上类RMQ问题：树链剖分

连通性

网络

最大流-最小割：网络最大流
最小费用最大流

二分图

最大匹配：匈牙利算法-二分图匹配，费用流法-最小费用最大流 4.1
最大点全覆盖集：最小费用最大流 4.2
最大独立集：最小费用最大流 4.3

欧拉图：欧拉路

x 1#include2#include3#include4#include5using namespace std;67const int CN = 6e5+5;89int read(){10 int s = 0,ne = 1; char c = getchar();11 while(c < ‘0’ || c > ‘9’) ne = c == ‘-‘ ? -1 : 1, c = getchar();12 while(c >= ‘0’ && c <= ‘9’) s = (s << 1) + (s << 3) + c - ‘0’, c = getchar();13 return s * ne;14}1516class fs {public: int to,nxt; void init(int t,int n) {to = t, nxt = n;}}E[CN << 2];17int hd[CN],ecnt = 0; void add(int x,int y) {E[++ecnt].init(y, hd[x]); hd[x] = ecnt;}1819class trie{ // dep = 0,dep > 2020 public: int ch[CN * 30][2], w[CN * 30], val[CN * 30], rt[CN], tot;21 trie() {memset(rt, 0, sizeof(rt)); tot = 0;}22 #define lc ch[u][0]23 #define rc ch[u][1]24 int make() {int u = ++tot; lc = rc = w[u] = val[u] = 0; return tot;}25 void maintain(int u){26 w[u] = val[u] = 0;27 if(lc) w[u] += w[lc], val[u] ^= val[lc] << 1;28 if(rc) w[u] += w[rc], val[u] ^= (val[rc] << 1) | w[rc];29 w[u] &= 1;30 }31 void ins(int &u,int x,int dep){32 if(!u) u = make();33 if(dep > 20) return (void)(w[u] ^= 1);34 ins(ch[u][x & 1], x >> 1, dep + 1);35 maintain(u);36 }37 void addall(int u) {if(rc) addall(rc); swap(lc, rc); maintain(u);}38 int merge(int u,int k){39 if(!k) return u; if(!u) return k;40 w[u] = (w[u] + w[k]) & 1; val[u] ^= val[k];41 lc = merge(lc, ch[k][0]); rc = merge(rc, ch[k][1]);42 return u;43 }44}D;4546int n,v[CN],va[CN];4748void dfs(int u){49 if(!hd[u]){50 va[u] = v[u];51 D.ins(D.rt[u], v[u], 0);52 return;53 }5455 int k = hd[u], s1;56 for(; k; k = E[k].nxt) dfs(E[k].to);57 58 k = hd[u], s1 = E[k].to, k = E[k].nxt, D.rt[u] = D.rt[s1];59 for(; k; k = E[k].nxt){60 int v = E[k].to;61 D.merge(D.rt[u], D.rt[v]);62 }63 D.addall(D.rt[u]), D.ins(D.rt[u], v[u], 0);64 va[u] = D.val[ D.rt[u] ];65}6667int main()68{69 n = read();70 for(int i = 1;i <= n;i++) v[i] = read();71 for(int i = 2;i <= n;i++) add(read(), i);7273 dfs(1);7475 long long ans = 0;76 for(int i = 1;i <= n;i++) ans += 1ll * va[i];7778 printf(“%lld”, ans); 79}cpp