题目给的是一个n条边的连通图,容易知道他是一个基环树,断掉基环树的一条边。

考虑树链剖分维护路径的权值和,每次询问拆成三次,分别是直接到达和两种通过环边到达的路径距离最小值即为答案。

注意:树链剖分的写法和边的记录,边权和点权的转化(边权转化为子节点的点权)。

阅读全文 »

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int f[maxn], inv[maxn], finv[maxn];
void init(){
inv[1] = 1;
for (int i = 2; i < maxn; i++) inv[i] = (mod - mod / i) * 1ll * inv[mod % i] % mod;
f[0] = finv[0] = 1;
for (int i = 1; i < maxn; i++) {
f[i] = f[i - 1] * 1ll * i % mod;
finv[i] = finv[i - 1] * 1ll * inv[i] % mod;
}
}
int C(int n, int m){
if (m < 0 || m > n) return 0;
return f[n] * 1ll * finv[n - m] % mod * finv[m] % mod;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
struct edge{
int to, nxt, d;
bool operator<(const edge& b)const {
return d > b.d;
}
}f[20 * maxn];
int head[maxn], tot = 0;
void add(int x, int y, int d){
f[++tot].to = y; f[tot].d = d; f[tot].nxt = head[x]; head[x] = tot;
}

int p, r, vis[maxn];
int prim(){
ms(vis, 0); vis[1] = 1;
priority_queue<edge> q;
int ans = 0;
for (int i = head[1]; i; i = f[i].nxt){
q.push(f[i]);
}
while (!q.empty()){
edge t = q.top(); q.pop();
if (vis[t.to]) continue;
vis[t.to] = 1;
ans += t.d;
for (int i = head[t.to]; i; i = f[i].nxt){
q.push(f[i]);
}
}
return ans;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct edge{char x, y; int d;};
bool cmp(const edge& a, const edge& b){
return a.d < b.d;
}
vector<edge> v;

int n, pre[maxn];
void init(){
for (int i = 0; i < maxn; i++) pre[i] = i;
}
int find(int x){return x == pre[x] ? x : pre[x] = find(pre[x]);}
void join(int x, int y){
x = find(x), y = find(y);
pre[x] = y;
}
int kruskal(){
sort(v.begin(), v.end(), cmp);
int ans = 0;
for (int i = 0, a, b; i < v.size(); i++){
a = find(v[i].x - 'A'), b = find(v[i].y - 'A');
if (a == b) continue;
join(a, b); ans += v[i].d;
}
return ans;
}

注意

  • 区间翻转的 lazy 标记的下推

  • findroot() 会修改树的结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#define void inline void
const int maxn = 300000 + 5;

int n, m, a[maxn];

struct lct {
int fa[maxn], ch[maxn][2], rev[maxn], s[maxn];
int nroot(int x) { return ch[fa[x]][0] == x || ch[fa[x]][1] == x; }
int get(int x) { return ch[fa[x]][1] == x; }
void pushup(int x) {
s[x] = s[ch[x][0]] ^ s[ch[x][1]] ^ a[x];
}
void pushrev(int x) {
swap(ch[x][0], ch[x][1]);
rev[x] ^= 1;
}
void pushdown(int x) {
if (!rev[x]) return;
if (ch[x][0]) pushrev(ch[x][0]);
if (ch[x][1]) pushrev(ch[x][1]);
rev[x] = 0;
}
void rot(int x) {
int old = fa[x], oldf = fa[old], k = get(x), w = ch[x][k ^ 1];
if (nroot(old)) ch[oldf][ch[oldf][1] == old] = x;
ch[x][k ^ 1] = old; ch[old][k] = w;
if (w) fa[w] = old;
fa[old] = x; fa[x] = oldf;
pushup(old);
}
int st[maxn];
void splay(int x) {
int y = x, t = 0;
st[++t] = y;
while (nroot(y)) st[++t] = fa[y], y = fa[y];
while (t) pushdown(st[t--]);
while (nroot(x)) {
y = fa[x];
if (nroot(y)) rot(get(x) == get(y) ? y : x);
rot(x);
}
pushup(x);
}
void access(int x) {
for (int y = 0; x; y = x, x = fa[x])
splay(x), ch[x][1] = y, pushup(x);
}
void make(int x) {
access(x); splay(x); pushrev(x);
}
int findroot(int x) {
access(x); splay(x); // findroot 把待检查的元素转上去了
while (ch[x][0]) pushdown(x), x = ch[x][0];
// splay(x); // ?
return x;
}
void split(int x, int y) {
make(x); access(y); splay(y);
}
int link(int x, int y) {
make(x);
if (findroot(y) == x) return 0;
fa[x] = y;
return 1;
}
int cut(int x, int y) {
// split(x, y); fa[x] = ch[y][0] = 0; pushup(y);
make(x);
if (findroot(y) != x || fa[x] != y || ch[x][1]) return 0;
// if (findroot(y) != x || size[y] > 2) return 0;
fa[x] = ch[y][0] = 0;
pushup(y);
return 1;
}
int qpath(int l, int r) { split(l, r); return s[r]; }
void upoint(int x, int y) { splay(x); a[x] = y; }
} f;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
struct fhqTreap{
int ch[maxn][2], size[maxn], key[maxn], rnd[maxn], rev[maxn], root, tot;
fhqTreap(){ root = tot = 0; }
void clear(){ root = tot = 0; }
int node(int v, int x){
key[++tot] = v; rnd[tot] = rand();
size[tot] = 1; ch[tot][0] = ch[tot][1] = rev[tot] = 0;
return tot;
}
void pushup(int x){size[x] = size[ch[x][0]] + size[ch[x][1]] + 1;}
void pushdown(int x){
if (!rev[x]) return;
swap(ch[x][0], ch[x][1]);
if (ch[x][0]) rev[ch[x][0]] ^= 1;
if (ch[x][1]) rev[ch[x][1]] ^= 1;
rev[x] = 0;
}
void split(int now, int k, int &x, int &y){
if (!now) {
x = y = 0; return;
}
pushdown(now);
if (size[ch[now][0]] < k){
x = now;
split(ch[now][1], k - size[ch[now][0]] - 1, ch[now][1], y);
}
else {
y = now;
split(ch[now][0], k, x, ch[now][0]);
}
pushup(now);
}
int merge(int x, int y){
if (!x || !y) return x + y;
if (rnd[x] < rnd[y]){
pushdown(x);
ch[x][1] = merge(ch[x][1], y);
pushup(x); return x;
}
else {
pushdown(y);
ch[y][0] = merge(x, ch[y][0]);
pushup(y); return y;
}
}
void reverse(int l, int r){
int x, y, z;
split(root, l - 1, x, y);
split(y, r - l + 1, y, z);
rev[y] ^= 1;
root = merge(x, merge(y, z));
}
void print(int x){
if (!x) return;
pushdown(x);
print(ch[x][0]);
v.push_back(key[x]);
print(ch[x][1]);
}
}f;

枚举映射。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
struct edge{int x, y;};
using G = vector<edge>;

inline G read(int m){
G a;
for (int i = 0; i < m; i++){
int x, y; scanf("%d%d", &x, &y);
a.push_back(edge {x, y});
}
return a;
}
inline int count(const G& b, const G& a){
ms(vis, 0);
for (int i = 0; i < a.size(); i++) vis[a[i].x][a[i].y] = vis[a[i].y][a[i].x] = 1;
for (int i = 0; i <= n; i++) f[i] = i;
int res = 0;
do{
bool flag = true;
for (int i = 0; i < b.size(); i++){
if (!vis[f[b[i].x]][f[b[i].y]]){
flag = false; break;
}
}
if (flag) res++;
} while (next_permutation(f + 1, f + 1 + n));
return res;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
struct fhqTreap {
int ch[maxn][2], key[maxn], rnd[maxn], size[maxn], root, tot;
fhqTreap() { root = tot = 0; }
void clear() { root = tot = 0; }
int node(int v) {
key[++tot] = v; rnd[tot] = rand();
size[tot] = 1;
ch[tot][0] = ch[tot][1] = 0;
return tot;
}
void pushup(int x) { size[x] = size[ch[x][0]] + size[ch[x][1]] + 1; }
void split(int now, int k, int &x, int &y) {
if (!now) {
x = y = 0; return;
}
if (key[now] <= k) {
x = now;
split(ch[now][1], k, ch[now][1], y);
} else {
y = now;
split(ch[now][0], k, x, ch[now][0]);
}
pushup(now);
}
int merge(int x, int y) {
if (x == 0 || y == 0) return x + y;
if (rnd[x] < rnd[y]) {
ch[x][1] = merge(ch[x][1], y);
pushup(x); return x;
} else {
ch[y][0] = merge(x, ch[y][0]);
pushup(y); return y;
}
}
void insert(int v) {
int x = 0, y = 0;
split(root, v, x, y);
root = merge(merge(x, node(v)), y);
}
void del(int v) {
int x = 0, y = 0, z = 0;
split(root, v, x, z);
split(x, v - 1, x, y);
y = merge(ch[y][0], ch[y][1]);
root = merge(merge(x, y), z);
}
int find(int v) {
int x = 0, y = 0;
split(root, v - 1, x, y);
int ans = size[x] + 1;
root = merge(x, y);
return ans;
}
int findx(int now, int rank) {
while (1) {
if (size[ch[now][0]] >= rank) now = ch[now][0];
else if (size[ch[now][0]] + 1 == rank) return key[now];
else {
rank -= size[ch[now][0]] + 1;
now = ch[now][1];
}
}
}
int prev(int v) {
int x = 0, y = 0;
split(root, v - 1, x, y);
int ans = findx(x, size[x]);
root = merge(x, y);
return ans;
}
int succ(int v) {
int x = 0, y = 0;
split(root, v, x, y);
int ans = findx(y, 1);
root = merge(x, y);
return ans;
}
} f;

  • 度数总和为偶数。

  • 对度数序列排序,将度数最大顶点连到其他顶点上,如果出现负度数,则构造失败。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn = 1000 + 5;

int n, a[maxn];

int main(){
int T; scanf("%d", &T);
while (T--){
scanf("%d", &n);
int s = 0;
for (int i = 0; i < n; i++) scanf("%d", &a[i]), s += a[i];
if (s % 2){
puts("no"); continue;
}
int flag = 1;
for (int i = 0; i < n && flag; i++){
sort(a, a + n, [](int a, int b){return a > b;});
if (a[0] == 0) break;
for (int j = 0; j < a[0]; j++){
a[j + 1]--;
if (a[j + 1] < 0) {
flag = 0; break;
}
}
a[0] = 0;
}
if (flag) puts("yes");
else puts("no");
}
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn = 100000 + 5;

struct edge{int to, nxt;}f[4 * maxn];
int head[maxn], cnt;
void add(int x, int y){
f[++cnt].to = y; f[cnt].nxt = head[x]; head[x] = cnt;
}

int n, m, q;
int tot = 0, dfn[maxn], low[maxn], dep[maxn], fa[maxn];
int cut[maxn], br;

void dfs(int p, int old){
dfn[p] = low[p] = ++tot;
dep[p] = dep[old] + 1;
for (int i = head[p]; i; i = f[i].nxt){
int v = f[i].to;
if (v == old) continue;
if (!dfn[v]){
fa[v] = p; dfs(v, p);
low[p] = min(low[p], low[v]);
if (low[v] > dfn[p]){
cut[v] = 1;
br++;
}
}
else low[p] = min(low[p], dfn[v]);
}
}

void lca(int x, int y){
if (dfn[x] < dfn[y]) swap(x, y);
while (dfn[x] > dfn[y]){
if (cut[x]) {
br--; cut[x] = 0;
}
x = fa[x];
}
while (x != y){
if (cut[x]){
br--; cut[x] = 0;
}
if (cut[y]){
br--; cut[y] = 0;
}
x = fa[x]; y = fa[y];
}
}

void init(){
ms(head, 0); cnt = 0;
ms(dfn, 0); tot = 0;
ms(cut, 0); br = 0;
dep[0] = fa[1] = 0;
}

int main(){
int kase = 0;
while (~scanf("%d%d", &n, &m)){
if (!n && !m) break;
init();
while (m--){
int x, y; scanf("%d%d", &x, &y);
add(x, y); add(y, x);
}
dfs(1, 0);
scanf("%d", &q);
printf("Case %d:\n", ++kase);
int kas = 0;
while (q--){
int x, y; scanf("%d%d", &x, &y);
lca(x, y); printf("%d\n", br);
}
puts("");
}
return 0;
}