9 月 | 2019 | 杰克部落

朴素算法：洛谷70分,O2 80分

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

#include<iostream>
#include<vector>
using namespace std;
int n, m, s;
vector<int> edges[500005];
int father[500005],depth[500005];
void dfs(int node, int fath) {
father[node] = fath;
depth[node] = depth[fath] + 1;
for (int i = 0; i < edges[node].size(); i++) {
if (edges[node][i] == fath)continue;
dfs(edges[node][i], node);
}
}
int query(int a, int b) {
while (a != b) {
if (depth[a] >= depth[b])a = father[a];
else b = father[b];
}
return a;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> s;
for (int i = 1; i <= n - 1; i++) {
int x, y;
cin >> x >> y;
edges[x].push_back(y);
edges[y].push_back(x);
}
dfs(s, s);
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
cout << query(a, b) << "\n";
}
}

倍增：洛谷80分，O2 100分

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

#include<iostream>
#include<vector>
#include<algorithm>
#define MAXLOG 20
using namespace std;
int n, m, s;
vector<int> edges[500005];
int depth[500005];
int ancestor[500005][MAXLOG+2];
void dfs(int node, int fath) {
ancestor[node][0] = fath;
depth[node] = depth[fath] + 1;
for (int i = 1; i <= MAXLOG; i++)ancestor[node][i] = ancestor[ancestor[node][i - 1]][i - 1];
for (int i = 0; i < edges[node].size(); i++) {
if (edges[node][i] == fath)continue;
dfs(edges[node][i], node);
}
}
int query(int a, int b) {
if (depth[b] > depth[a])swap(a, b);
for (int i = MAXLOG; ~i; i--)if (depth[ancestor[a][i]] >= depth[b])a = ancestor[a][i];
if (a == b)return a;
for (int i = MAXLOG; ~i; i--) if(ancestor[a][i]!=ancestor[b][i]){
a = ancestor[a][i];
b = ancestor[b][i];
}
return ancestor[a][0];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> s;
for (int i = 1; i <= n - 1; i++) {
int x, y;
cin >> x >> y;
edges[x].push_back(y);
edges[y].push_back(x);
}
dfs(s, s);
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
cout << query(a, b) << "\n";
}
}

Tarjan:洛谷70分，O2 100分

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

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
int n, m, s;
vector<int> edges[500005],askPair[500005];
bool visited[500005];
int father[500005];
inline int _find(int node) {
if (father[node]==-1)return node;
return father[node] = _find(father[node]);
}
inline void _union(int x, int y) {
if(_find(x)!=_find(y))father[_find(x)] = y;
}
struct ask {
int u, v;
int ans;
}asks[500005];
inline int checkV(int id,int node) {
if (asks[id].u != node)return asks[id].u;
return asks[id].v;
}
void dfs(int node,int fath) {
for (int i = 0; i < edges[node].size(); i++) {
if (edges[node][i] == fath)continue;
dfs(edges[node][i],node);
_union(edges[node][i], node);
}
visited[node] = true;
for (int i = 0; i < askPair[node].size(); i++) {
int v = checkV(askPair[node][i], node);
if (visited[v])asks[askPair[node][i]].ans = _find(v);
}
}
int main() {
memset(father, -1, sizeof(father));
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> s;
for (int i = 1; i <= n - 1; i++) {
int x, y;
cin >> x >> y;
edges[x].push_back(y);
edges[y].push_back(x);
}
for (int i = 1; i <= m; i++) {
cin >> asks[i].u >> asks[i].v;
askPair[asks[i].u].push_back(i);
askPair[asks[i].v].push_back(i);
}
dfs(s,s);
for (int i = 1; i <= m; i++)cout << asks[i].ans << "\n";
}

原题链接：https://nanti.jisuanke.com/t/41392
竟然做出来一道这么复杂的概率+DFS+逆元题，开心到爆炸，特此发题解一篇^v^

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

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#define MOD 1000000007
#define ll long long
using namespace std;
int n;
int MDep;
vector<int> edges[1000005];
bool visited[1000005];
ll quickpow(ll a, ll b) {
if (b == 0)return 1;
ll re = quickpow(a, b / 2) % MOD;
re = (re * re) % MOD;
if (b % 2 == 1)re *= a % MOD;
return re % MOD;
}
inline ll inv(ll x) {
return quickpow(x, MOD - 2) % MOD;
}
inline ll chance1(ll TotNode) {
ll ch = (inv(TotNode)) % MOD;
return ch;
}
inline ll chance2(ll onceCh,ll TotNode) {
ll onceNonch = (1ll-onceCh+MOD) % MOD;
ll nonch = quickpow(onceNonch, TotNode);
ll fin = (1ll - nonch + MOD) % MOD;
return fin;
}
int dfsMaxDep(int node) {
int maxDep = 1;
bool hasChild = false;
visited[node] = true;
for (int i = 0; i < edges[node].size(); i++) {
if (visited[edges[node][i]])continue;
hasChild = true;
maxDep = max(maxDep, dfsMaxDep(edges[node][i]) + 1);
}
return maxDep;
}
ll dfsChance(int depth,int node){
if (depth == MDep)return 1;
ll ch = 0,sCh=chance1(node==1?edges[node].size(): edges[node].size()-1);
visited[node] = true;
for (int i = 0; i < edges[node].size(); i++) {
if (visited[edges[node][i]])continue;
ll CurCH = dfsChance(depth + 1, edges[node][i]);
if (CurCH) {
ch += (CurCH * sCh) % MOD;
ch %= MOD;
}
}
return chance2(ch, node == 1 ? edges[node].size() : edges[node].size() - 1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
edges[u].push_back(v);
edges[v].push_back(u);
}
MDep = dfsMaxDep(1);
memset(visited, false, sizeof(visited));
ll ch = dfsChance(1, 1);
cout << ch;
}

杰克部落

梦想本不会发光，发光的是追梦的你

月度归档：2019年09月

洛谷 P3379 【模板】最近公共祖先（LCA）重写

计蒜客 Random Access Iterator

2019 年 9 月
一	二	三	四	五	六	日
						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