牛客周赛103

F

\hspace{15pt}小红定义一棵树的其中一棵子树[1]^\texttt{[1]}的权值为：将子树的所有节点编号从小到大排序后，形成数组的不动点[2]^\texttt{[2]}数量。
\hspace{15pt}现在小红拿到了一棵有 nn 个节点，以 nn 为根的树，他想知道这棵树的所有子树的权值之和，请你帮帮他。

【名词解释】
\hspace{15pt}子树[1]^\texttt{[1]}：树中某节点删掉与父亲相连的边后，该节点所在的子图。
\hspace{15pt}不动点[2]^\texttt{[2]}：定义整数 i(1≦i≦m)i\left(1\leqq i \leqq m \right) 是长度为 mm 的数组 {a1,a2,…,am}\{a_1,a_2,\dots,a_m\} 的一个不动点，当且仅当满足 ai=ia_i = i。

\hspace{15pt}第一行输入一个整数 n(1≦n≦2×105)n\left(1\leqq n \leqq 2\times 10^5 \right)，代表树的节点数量。
\hspace{15pt}此后 n−1n - 1 行，第 ii 行输入两个整数 ui,vi(1≦ui,vi≦n)u_i,v_i(1\leqq u_i,v_i\leqq n)，表示第 ii 条树边连接节点 uiu_i 和 viv_i。

\hspace{15pt}输出一个整数，代表子树权值之和。

思路
LCA+贡献法

贡献法的思路和E题一样，都是从区间[1,1][1,1]加到[1,n][1,n]，把每个数的贡献拆开到每个区间里，对每个区间的出现次数进行累加。

该题的背景是在一颗树上，我们观察可以发现，对于区间[1,2][1,2]，我们要求出1和2的LCA，区间[1,2][1,2]的贡献就是它们LCA的深度，也就是有深度棵子树包含这个区间。所以不断维护当前的数ii和上一个LCA结合成的新的LCA，然后累加LCA的深度就是答案。

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pull = pair<ull,ull>;
using vec = vector<int>;
using vec2 = vector<vector<int>>;
using vecl = vector<ll>; 
using maii = map<int,int>;
#define pb(x) push_back(x) 
#define eb(x) emplace_back(x)
const int maxn = 2e5+5;
int n;

vec d(maxn), e[maxn];
vec2 f(maxn, vec(25));

void dfs(int u, int fa){
    d[u] = d[fa] + 1;
    f[u][0] = fa;
    for(int i=1;i<=20;i++)
        f[u][i] = f[f[u][i-1]][i-1];
    for(auto v:e[u])
        if(v != fa) dfs(v, u);
}

int lca(int a, int b){
    if(d[a] < d[b]) swap(a, b);
    for(int i=20;~i;i--)
        if(d[f[a][i]] >= d[b]) a = f[a][i];
    if(a == b) return b;
    for(int i=20;~i;i--)
        if(f[a][i] != f[b][i]) a = f[a][i], b = f[b][i];
    return f[a][0];
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++){
        int a, b; cin >> a >> b;
        e[a].eb(b), e[b].eb(a);
    }
    dfs(n,0);
    ll ans = 0;
    int c = 1;
    for(int i=1;i<=n;i++){
        c = lca(i, c);
        ans += 1LL*d[c];
    }
    cout << ans << '\n';
    return 0;
}

E

\hspace{15pt}小红定义一个数组的权值为：将其从小到大排序后，不动点[1]^\texttt{[1]}的数量。
\hspace{15pt}现在，小红拿到了一个长为 nn 的排列[2]^\texttt{[2]}，他想知道其所有子数组[3]^\texttt{[3]}的权值之和，请你帮帮她。

【名词解释】
\hspace{15pt}不动点[1]^\texttt{[1]}：定义整数 i(1≦i≦m)i\left(1\leqq i \leqq m \right) 是长度为 mm 的数组 {a1,a2,…,am}\{a_1,a_2,\dots,a_m\} 的一个不动点，当且仅当满足 ai=ia_i = i。
\hspace{15pt}排列[2]^\texttt{[2]}：长度为 nn 的排列是由 1,2,…,n1,2,\dots,n 这 nn 个整数、按任意顺序组成的数组（每个整数均恰好出现一次）。例如，{2,3,1,5,4}\{2,3,1,5,4\} 是一个长度为 55 的排列，而 {1,2,2}\{1,2,2\} 和 {1,3,4}\{1,3,4\} 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。
\hspace{15pt}子数组[3]^\texttt{[3]}：从原数组中，连续的选择一段元素（可以全选、可以不选）得到的新数组。

\hspace{15pt}第一行输入一个整数 n(1≦n≦3×105)n\left( 1\leqq n \leqq 3 \times 10^5\right)，代表排列中的元素数量。
\hspace{15pt}第二行输入 nn 个互不相同的整数 a1,a2,…,an(1≦ai≦n)a_1,a_2,\dots,a_n\left(1\leqq a_i \leqq n\right)，代表一个排列。

\hspace{15pt}输出一个整数，代表子数组权值之和。

思路

容易想到贡献法

我们可以发现，如果数k有贡献的话，那么区间[1,k][1,k]内的数都要存在，k才会有贡献。

接着推下去，区间[1,k][1,k]内的数都要存在，也就是说数1、2…k都要存在，那么数1、2…k-1肯定存在，那么数1、2…k-2肯定存在…那么数1、2肯定存在，那么数1肯定存在。

所以数k要有贡献，那么它所在的区间必然有数1，然后有数2…然后有数k。

所以我们就将数1…n出现的下标记录下来，然后用mi维护区间[1,i][1,i]内的最小值，用ma维护区间[1,i][1,i]内的最大值。区间[1,i][1,i]的贡献就是位于区间左边的数L和右边的数R。L的数量有mi个，R的数量有n-ma+1个，所以这段区间的贡献就是mi∗(n−ma+1)mi*(n-ma+1)

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pull = pair<ull,ull>;
using vec = vector<int>;
using vec2 = vector<vector<int>>;
using vecl = vector<ll>; 
using maii = map<int,int>;
#define pb(x) push_back(x) 
#define eb(x) emplace_back(x)
const int maxn = 3e5+5;

vec a(maxn), b(maxn);

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n; cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        b[a[i]] = i;
    }
    ll ans = 0;
    int mi = 0x3f3f3f3f, ma = 0;
    for(int i=1;i<=n;i++){
        mi = min(mi, b[i]), ma = max(ma, b[i]);
        ans += 1LL * mi * (n - ma + 1);
    }
    cout << ans << '\n';
    return 0;
}

D

\hspace{15pt}小红拿到了一个 nn 行 mm 列的矩阵，她希望其中的矩阵不动点尽可能多，为此她可以进行至多一次如下操作：
∙ \hspace{23pt}\bullet\,选择两个不同位置上，将它们上的元素交换。
\hspace{15pt}请你帮小红求出能得到的最大矩阵不动点数量。

【名词解释】
\hspace{15pt}矩阵不动点：定义整数二元组 {i,j}(1≦i≦n,1≦j≦m)\{i,j\} \left(1\leqq i \leqq n,1\leqq j \leqq m \right) 是 nn 行 mm 列的矩阵 [a1,1a1,2⋯a1,ma2,1a2,2⋯a2,m⋮⋮⋱⋮an,1an,2⋯an,m]\begin{bmatrix}a_{1,1} & a_{1,2} & \cdots & a_{1,m} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,m}\end{bmatrix} 的一个矩阵不动点，当且仅当满足 ai,j=min⁡(i,j)a_{i,j} = \min(i,j)。

\hspace{15pt}第一行输入两个整数 n,m(1≦n,m≦500)n,m\left(1 \leqq n, m\leqq 500 \right)，代表矩阵的行数和列数。
\hspace{15pt}此后 nn 行，第 ii 行输入 mm 个正整数 ai,1,ai,2,…,ai,m(1≦ai,j≦500)a_{i,1},a_{i,2},\dots,a_{i,m} \left(1\leqq a_{i,j} \leqq 500 \right)，其中，ai,ja_{i,j} 代表矩阵的第 ii 行第 jj 列的元素。

\hspace{15pt}输出一个整数，代表能得到的最大矩阵不动点数量。

思路

题目说最多交换一次，这一次交换可能带来的增益是2，1，0。

  • 如果我当前的位置index提供的数a[i][j]，能够与和我交换的数a[i][j]所提供的index对应上，那么增益就为2；

  • 在上面的情况对应不上的情况下，如果我提供的数a[i][j]没有超出矩阵n、m的范围，也就是a[i][j] <= min(n,m)，那么我把数a[i][j]交换过去之后，带来的增益是1。

  • 最后一种情况，那就是对应不上，无法交换，那么增益就为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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pull = pair<ull,ull>;
using vec = vector<int>;
using vec2 = vector<vector<int>>;
using vecl = vector<ll>; 
using maii = map<int,int>;
#define pb(x) push_back(x) 
#define eb(x) emplace_back(x)
const int maxn = 505;

vec2 a(maxn, vec(maxn));
vector <vector<bool>> sh(maxn, vector<bool>(maxn));

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n, m; cin >> n >> m;
    int ans = 0, add = 0;
    for(int i=1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            cin >> a[i][j];
            int index = min(i, j);
            if(a[i][j] == index) ans++;
            else{
                sh[index][a[i][j]] = 1;
                if(sh[a[i][j]][index]) add = 2;
                else if(a[i][j] <= min(n, m)) add = max(add, 1);
            }
        }
    }
    cout << ans + add << '\n';
    return 0;
}

C

\hspace{15pt}小红拿到了 2×n2\times n 个元素，现在她想将这些元素划分为两组（每组恰好 nn 个元素），且两组内部的顺序均可任意重排。
\hspace{15pt}她想知道，这两个数组的不动点数量之和最多是多少，请你帮帮她。

【名词解释】
\hspace{15pt}不动点：定义整数 i(1≦i≦m)i\left(1\leqq i \leqq m \right) 是长度为 mm 的数组 {a1,a2,…,am}\{a_1,a_2,\dots,a_m\} 的一个不动点，当且仅当满足 ai=ia_i = i。

\hspace{15pt}第一行输入一个整数 n(1≦n≦2×105)n \left(1 \leqq n \leqq 2\times10^5 \right)。
\hspace{15pt}第二行输入 2×n2\times n 个正整数 a1,a2,…,a2×n(1≦ai≦2×105)a_1,a_2,\dots,a_{2\times n} \left(1\leqq a_i \leqq 2\times 10^5 \right)，代表数组中的元素。

\hspace{15pt}输出一个整数，代表两个数组的不动点数量之和的最大值。

思路

这题！出题人！语文！是体育老师教的！

且看题目第二小句"划分为两组"，这能叫划分吗？划分是指在给出的数列中的任意两个数之间断开，从而将这一段连续的数列拆分为两段。

但这道题的正确做法是从这2n个数里面选取n个数，选两次。这是选取不是划分！(害得我wa好几发)

吐槽完出题人的语文水平之后，来看这道题的解题思路。贪心，每个数最多选择两次，我们先用哈希表存下每个数的出现的次数；然后对每个数进行判断：如果这个数的大小是小于n的，那么就可以作为不动点，ans就加上这个数的数量，由于每个数最多选两次，所以这个数的数量大于2时我们加2即可。

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pull = pair<ull,ull>;
using vec = vector<int>;
using vec2 = vector<vector<int>>;
using vecl = vector<ll>; 
using maii = map<int,int>;
#define pb(x) push_back(x) 
#define eb(x) emplace_back(x)
const int maxn = 2e5+5;
unordered_map <int,int> uma;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n; cin >> n;
    for(int i=1;i<=2*n;i++){
        int c; cin >> c;
        uma[c]++;
    }
    int ans = 0;
    for(auto &[x,y]:uma){
        if(x <= n) ans += min(y,2); 
    }
    cout << ans << '\n';
    return 0;
}

B

\hspace{15pt}小红希望得到一个长为 nn 的排列[1]^\texttt{[1]}，其中恰好有 kk 个不动点[2]^\texttt{[2]}。
\hspace{15pt}请你帮她找到一个符合条件的排列。

【名词解释】
\hspace{15pt}排列[1]^\texttt{[1]}：长度为 nn 的排列是由 1,2,…,n1,2,\dots,n 这 nn 个整数、按任意顺序组成的数组（每个整数均恰好出现一次）。例如，{2,3,1,5,4}\{2,3,1,5,4\} 是一个长度为 55 的排列，而 {1,2,2}\{1,2,2\} 和 {1,3,4}\{1,3,4\} 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。
\hspace{15pt}不动点[2]^\texttt{[2]}：定义整数 i(1≦i≦m)i\left(1\leqq i \leqq m \right) 是长度为 mm 的数组 {a1,a2,…,am}\{a_1,a_2,\dots,a_m\} 的一个不动点，当且仅当满足 ai=ia_i = i。

\hspace{15pt}第一行输入两个整数 n,k(1≦n≦10; 0≦k≦n)n, k\left(1\leqq n\leqq 10;\ 0\leqq k \leqq n\right)，代表排列的长度、不动点数量。

\hspace{15pt}如果无法构造符合条件的排列，请输出 −1-1，否则输出 nn 个整数，代表一个符合条件的排列。
\hspace{15pt}如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

思路

题目是不难的，毕竟B题也是一道签到。但坑点比较多，容易因为一时的冒进导致WA。作为一道签到题，通过率只有[1213/5101]，数据可以说明这题有多坑了。

我最初也小看了这道题，导致我交了很多WA…一个坑点是当k + 1 == n时，是构造不出来的，因为剩下的一个点一定是一个不动点，不可能是动点。另外的坑就是在构造的时候，如果动点的数量为奇数，那么就不能直接按照“逆转排列”来构造，由于奇数的对称性，位于正中间的数在“逆转排列”的情况下是一个不动点，不符合要求的。这个时候就需要其它的构造法了，随你怎么造都行，只要不踩坑。

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pull = pair<ull,ull>;
using vec = vector<int>;
using vec2 = vector<vector<int>>;
using vecl = vector<ll>; 
using maii = map<int,int>;
#define pb(x) push_back(x) 
#define eb(x) emplace_back(x)

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n ,k;
    cin >> n >> k;
    if(k + 1 == n) {cout << "-1\n"; return 0;}
    for(int i=1;i<=k;i++) cout << i << ' ';
    int si = n-k;
    if(si&1){
        for(int i=k+ceil(si/2.0);i<=n;i++) cout << i << ' ';
        for(int i=k+1;i<k+ceil(si/2.0);i++) cout << i << ' ';
    }
    else{
        for(int i=n;i>k;i--) cout << i << ' ';
    }
    cout << '\n';
    return 0;
}

A

\hspace{15pt}小红拿到了一个长为 44 的数组 {a1,a2,a3,a4}\{a_1,a_2,a_3,a_4\} ，他想知道其中有多少个不动点，请你帮帮她。

【名词解释】
\hspace{15pt}不动点：定义整数 i(1≦i≦m)i\left(1\leqq i \leqq m \right) 是长度为 mm 的数组 {a1,a2,…,am}\{a_1,a_2,\dots,a_m\} 的一个不动点，当且仅当满足 ai=ia_i = i。

\hspace{15pt}在一行上输入四个整数 a1,a2,a3,a4(1≦ai≦4)a_1,a_2,a_3,a_4 \left(1\leqq a_i \leqq4 \right)，代表数组。

\hspace{15pt}输出一个整数，代表数组不动点的数量。

思路
签到题不要思路

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pull = pair<ull,ull>;
using vec = vector<int>;
using vec2 = vector<vector<int>>;
using vecl = vector<ll>; 
using maii = map<int,int>;
#define pb(x) push_back(x) 
#define eb(x) emplace_back(x)

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    int cnt = 0;
    if(a == 1) cnt++;
    if(b == 2) cnt++;
    if(c == 3) cnt++;
    if(d == 4) cnt++;
    cout << cnt << '\n';
    return 0;
}

牛客暑期多校9

M

不难发现，数位和S(1723)=1+7+2+3S(1723) = 1 + 7 + 2 + 3满足运算S(a∗b)=S(a)∗S(b)S(a*b) = S(a) * S(b)
所以要使得

S(n∗a)=n∗S(a)S(n*a) = n*S(a)

就相当于

S(n)∗S(a)=n∗S(a)S(n) * S(a) = n * S(a)

即

S(n)=nS(n) = n

只有个位数满足这个运算，大于等于10都不行。对于aa，选择11就满足条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pull = pair<ull,ull>;
using vec = vector<int>;
using vecl = vector<ll>; 
using maii = map<int,int>;
#define pb(x) push_back(x) 
#define eb(x) emplace_back(x)

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        if(n >= 10) cout << "-1\n";
        else cout << "1\n";
    }
    return 0;
}

J

题干一大堆，结果是个签到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pull = pair<ull,ull>;
using vec = vector<int>;
using vecl = vector<ll>; 
using maii = map<int,int>;
#define pb(x) push_back(x) 
#define eb(x) emplace_back(x)

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    string s;
    while(getline(cin, s)){
        s = s + " nya";
        cout << s << '\n';
    }
    return 0;
}

F

我们令delx为起点和终点的x坐标和之差的绝对值，dely为起点和终点的y坐标和之差的绝对值。注意到，答案为这两者中最大的那个(因为每个示例都满足这个答案)，然后提交，发现过了，说明这个规律是正确的…

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pull = pair<ull,ull>;
using vec = vector<int>;
using vecl = vector<ll>; 
using maii = map<int,int>;
#define pb(x) push_back(x) 
#define eb(x) emplace_back(x)

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t; cin >> t;
    while(t--){
        ll sx1,sx2,sy1,sy2,tx1,tx2,ty1,ty2;
        cin >> sx1 >> sy1 >> sx2 >> sy2 >> tx1 >> ty1 >> tx2 >> ty2;
        ll delx = abs((sx1+sx2) - (tx1+tx2));
        ll dely = abs((sy1+sy2) - (ty1+ty2));
        ll ans = max(delx,dely);
        cout << ans << '\n';
    }
    return 0;
}

LCA

LCA(Lowest Common Ancestor)最近公共祖先，就是两个节点的公共祖先里面，离他们最近的那个祖先。

ST表倍增求解LCA

求解a，b两个点的LCA，你可能会想到暴力，这两个点一起，向它们的父节点跳，直到它们相遇，相遇的节点就是LCA。这种暴力的做法时间复杂度为O(n)O(n)，在竞赛中通常会TLE。

既然一步一步跳太慢，那么我们可以通过二进制拆分和倍增思想，一次跳一大步。在预处理之后，它能够一次性向上跳 2j2^j （j=0,1,2,...j=0, 1, 2, ...）步。预处理的时间复杂度为O(nlogn)O(nlogn)

我们定义：f[i][j]f[i][j] 表示：节点 i 向上跳 2j2^j 步后到达的祖先节点 ， d[i]d[i] 表示每个节点的深度。。

ff数组的求得方法是

  • 当 j = 0 时，fa[i][0] 就是 i 的父节点。
  • 对于 j > 0，我们把"向上跳2i2^i步"拆成两半来跳，分解为：先从 i 向上跳 2j−12^{j-1} 步，到达节点 k；再从节点 k 向上跳 2j−12^{j-1} 步。

于是，我们就得到了状态转移方程：

fa[i][j]=fa[fa[i][j−1]][j−1]fa[i][j] = fa[fa[i][j-1]][j-1]

这就是ST表的做法，通过二分、倍增的思想来优化区间查询，时间复杂度为O(mlogn)O(mlogn)，m为查询次数。

总时间复杂度O((n+m)logn)O((n+m)logn)。

以下是LCA模板题 洛谷P3379

P3379 【模板】最近公共祖先（LCA）

题目描述

如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

输入格式

第一行包含三个正整数 N,M,SN,M,S，分别表示树的结点个数、询问的个数和树根结点的序号。

接下来 N−1N-1 行每行包含两个正整数 x,yx, y，表示 xx 结点和 yy 结点之间有一条直接连接的边（数据保证可以构成树）。

接下来 MM 行每行包含两个正整数 a,ba, b，表示询问 aa 结点和 bb 结点的最近公共祖先。

输出格式

输出包含 MM 行，每行包含一个正整数，依次为每一个询问的结果。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
9
10
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

输出 #1

1
2
3
4
5
4
4
1
4
4

说明/提示

对于 30%30\% 的数据，N≤10N\leq 10，M≤10M\leq 10。

对于 70%70\% 的数据，N≤10000N\leq 10000，M≤10000M\leq 10000。

对于 100%100\% 的数据，1≤N,M≤5×1051 \leq N,M\leq 5\times10^5，1≤x,y,a,b≤N1 \leq x, y,a ,b \leq N，不保证 a≠ba \neq b。

以下是基于ST表的模板代码:

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pull = pair<ull,ull>;
using vec = vector<int>;
using vecl = vector<ll>; 
using maii = map<int,int>;
#define pb(x) push_back(x) 
#define eb(x) emplace_back(x)
const int maxn = 5e5+5;
int n, m, s, a, b;
vec e[maxn], d(maxn);
vector <vector<int>> f(maxn, vector<int>(25));

void dfs(int u,int father){
    d[u] = d[father] + 1;
    f[u][0] = father;
    for(int i=1;i<=20;i++)
        f[u][i] = f[f[u][i-1]][i-1];
    for(auto v:e[u])
        if(v != father) dfs(v,u);
}

int lca(int a, int b){
    if(d[a] < d[b]) swap(a, b);
    for(int i=20;~i;i--)
        if(d[f[a][i]] >= d[b]) a = f[a][i];
    if(a == b) return b;
    for(int i=20;~i;i--)
        if(f[a][i] != f[b][i]) a = f[a][i], b = f[b][i];
    return f[a][0];
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m >> s;
    for(int i=1;i<n;i++){
        cin >> a >> b;
        e[a].eb(b), e[b].eb(a);
    }
    dfs(s, 0);
    for(int i=1;i<=m;i++){
        int x, y; cin >> x >> y;
        cout << lca(x, y) << '\n';
    }
    return 0;
}

P3398

题目描述

小仓鼠的和他的基（mei）友（zi）sugar 住在地下洞穴中，每个节点的编号为 1∼n1\sim n。地下洞穴是一个树形结构。这一天小仓鼠打算从从他的卧室（aa）到餐厅（bb），而他的基友同时要从他的卧室（cc）到图书馆（dd）。他们都会走最短路径。现在小仓鼠希望知道，有没有可能在某个地方，可以碰到他的基友？

小仓鼠那么弱，还要天天被 zzq 大爷虐，请你快来救救他吧！

输入格式

第一行两个正整数 nn 和 qq，表示这棵树节点的个数和询问的个数。

接下来 n−1n-1 行，每行两个正整数 uu 和 vv，表示节点 uu 到节点 vv 之间有一条边。

接下来 qq 行，每行四个正整数 aa、bb、cc 和 dd，表示节点编号，也就是一次询问，其意义如上。

输出格式

对于每个询问，如果有公共点，输出大写字母 Y；否则输出N。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
9
10
5 5
2 5
4 2
1 3
1 4
5 1 5 1
2 2 1 4
4 1 3 4
3 1 1 5
3 5 1 4

输出 #1

1
2
3
4
5
Y
N
Y
Y
Y

思路

可以发现，如果这俩玩意能相遇，那么它们的路径一定有交点，而这个交点要么是a、b的LCA，要么是c、d的LCA。所以，当这个交点是a、b的LCA时，它也在c、d的路径上；当这个点是c、d的LCA时，它也在a、b的路径上。

所以我们先求出a、b的LCA，和c、d的LCA

现在问题转移到怎么判断这两个LCA在不在对方的路径上？这里用距离来判断：当节点zz在节点aa和bb之间的路径上时，它们的距离关系满足

dis(a,b)=dis(a,z)+dis(z,b)dis(a,b) = dis(a,z) + dis(z,b)

我们可以用LCA和深度来算距离，公式为

dis(x,y)=depth(x)+depth(y)−2×depth(lca(x,y))dis(x, y) = depth(x) + depth(y) - 2 \times depth(lca(x,y))

因此，满足以下两个条件之一，就是Yes:

  • a、b的LCA在路径cd上，即dis(c,d)=dis(c,lca(a,b))+dis(lca(a,b),d)dis(c,d) = dis(c,lca(a,b)) + dis(lca(a,b),d)
  • c、d的LCA在路径ab上，即dis(a,b)=dis(a,lca(c,d))+dis(lca(c,d),b)dis(a,b) = dis(a,lca(c,d)) + dis(lca(c,d),b)

以下是代码

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pull = pair<ull,ull>;
using vec = vector<int>;
using vec2 = vector<vector<int>>;
using vecl = vector<ll>; 
using maii = map<int,int>;
#define pb(x) push_back(x) 
#define eb(x) emplace_back(x)
const int maxn = 1e5+5;
int n, q;

vec e[maxn], d(maxn);
vec2 f(maxn, vector<int>(25));

void dfs(int u, int fa){
    d[u] = d[fa] + 1;
    f[u][0] = fa;
    for(int i=1;i<=20;i++)
        f[u][i] = f[f[u][i-1]][i-1];
    for(auto v:e[u])
        if(v != fa) dfs(v,u);
}

int lca(int a, int b){
    if(d[a] < d[b]) swap(a, b);
    for(int i=20;~i;i--){
        if(d[f[a][i]] >= d[b]) a = f[a][i];
    }
    if(a == b) return b;
    for(int i=20;~i;i--){
        if(f[a][i] != f[b][i]) a = f[a][i], b = f[b][i];
    }
    return f[a][0];
}

int dis(int a, int b){
    int c = lca(a, b);
    return d[a] + d[b] - 2*d[c];
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> q;
    for(int i=1, a, b;i<n;i++){
        cin >> a >> b;
        e[a].eb(b), e[b].eb(a);
    }
    dfs(1,0);
    for(int i=1, a, b, c ,dd;i<=q;i++){
        cin >> a >> b >> c >> dd;
        int x = lca(a, b), y = lca(c, dd);
        if((dis(a, b) == dis(a, y) + dis(b, y)) || (dis(c, dd) == dis(c,x) + dis(dd, x)))
            cout << "Y\n";
        else cout << "N\n";
    }
    return 0;
}