CF1276B
给你一张n个点m条边的无向图，给定两个点a和b，问有多少点对(x,y)之间的路径必须经过a和b两个点
x,y \(\neq\) a,b
\[1 \le n \le 2 *10^5, 1 \le m \le 5*10^5
\]
hint1 判断a,b都是割点
CF999E
给你一个n个点m条有向边的图，问最少加入多少边可以使得给定点\(v_0\)可以到达所有的点
\[1\le n,m \le 5000
\]
hint1 缩点
hint2 入度为0的点需要加入一条边，\(v_0\)所在点除外
CF1248F
给你n个人和n只猫，每个人和他对应编号的猫不能同时选中，给你m个关系，每个关系说明选中某个人和某只猫不能同时出现，你需要选出的猫和人的数量一共n个，且必须有1只猫和1个人，请给出是否可行以及方案
\[1\le n,m \le 10^6
\]
3 4
1 1
2 2
3 3
1 3
YES
2 1 //人数量和猫数量
1 3 // 人
2 // 猫
hint1 每个位置，不选人就选猫，反之亦然
hint2 选i号人指向j号人
hint3 只有一个强连通分量就无解
hint4 选出度为0的点选人，其余选猫
2-sat模板
给n个变量x（0， 1），有m个条件，每个条件形如[\(x_i\)为0或者\(x_j\)为1]，求一组满足所有条件的解
3 1
1 1 3 0 //a1 = 1 或者 a3 = 0
POSSIBLE
000
hint 1 x拆成01两个点，不满足\(x_i\)为0会使得\(x_j\)为1，把\(x_i\)的1点连向\(x_j\)的1，把\(x_j\)的0点连向\(x_i\)的0
hint2 缩点，若一个点的01在一个分量里面就无解
hint3 tarjan后，看每个点的0和1哪个颜色更大选哪个
重心与直径
树重心：割掉后，最大块最小，计算割去后最大块大小
- 换根dp
- dfs
dfs(int u, int f){siz[u] = 1;for(auto v:mp[u]){if(v == f) continue;dfs(v, u);siz[u] += siz[v];maxx = max(maxx, siz[v]);}maxx = max(maxx, n - siz[u]);if(maxx < ans){ans = maxx;G = u;}
}
补充：重心最大块小于\(\lfloor n/2 \rfloor\)，非重心最大块一定大于\(\lfloor n/2 \rfloor\)
树直径：树上距离最远的一对点(x,y)之间的路径
- 换根dp
- 两遍dfs，计算最远的点