10.24上课笔记

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哪个颜色更大选哪个

重心与直径

树重心：割掉后，最大块最小，计算割去后最大块大小

1. 换根dp
2. 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)之间的路径

1. 换根dp
2. 两遍dfs，计算最远的点