您的位置: 首页  >  IT文章  >  2021NUAA暑假集训 Day2 题解 A - 数的直径 B - Kay and Snowflake C - Fools and Roads D - Apple Tree E - Max Flow F - Count Descendants G - 信息传递 H - The Tag Game

2021NUAA暑假集训 Day2 题解 A - 数的直径 B - Kay and Snowflake C - Fools and Roads D - Apple Tree E - Max Flow F - Count Descendants G - 信息传递 H - The Tag Game

分类: IT文章 • 2023-11-05 22:32:44

比赛链接：21.7.13-NUAA暑期集训
比赛码：NUAAACM20210713

目录

两遍(dfs)，第一遍从根开始找到最深的结点，第二遍从最深的结点开始得到树的直径。

#include <cstring>
#include <iostream>
using namespace std;

struct Edge {
    int v, next;
} edge[200010];
int head[100010], cnt;
int n, dis[100010], start;

void addEdge(int u, int v) {
    edge[++cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt;
}

void dfs(int x, int fa) {
    for (int i = head[x]; i; i = edge[i].next) {
        int v = edge[i].v;
        if (v != fa) {
            dis[v] = dis[x] + 1;
            dfs(v, x);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        addEdge(x, y);
        addEdge(y, x);
    }
    memset(dis, 0x3f3f3f3f, sizeof(dis));
    dis[1] = 0;
    dfs(1, 0);
    int maxn = -1;
    for (int i = 1; i <= n; ++i) {
        if (dis[i] > maxn) {
            maxn = dis[i];
            start = i;  // 树的直径的起点
        }
    }
    memset(dis, 0x3f3f3f3f, sizeof(dis));
    dis[start] = 0;
    dfs(start, 0);
    maxn = -1;
    for (int i = 1; i <= n; ++i) {
        if (dis[i] > maxn) {
            maxn = dis[i];
        }
    }
    cout << maxn << endl;
    return 0;
}

B - Kay and Snowflake

一个树的重心，只会在根本身或者最大的子树当中产生。
先判断当前根能否作为重心，如果不能，就从最大的子树的重心往上面找。

#include <iostream>
#include <vector>
using namespace std;

int n, q, child[300010], Size[300010], res[300010], fa[300010];
vector<int> g[300010];

void dfs(int x) {
    Size[x] = 1;
    for (int i = 0; i < g[x].size(); ++i) {
        dfs(g[x][i]);
        Size[x] += Size[g[x][i]];
        if (Size[g[x][i]] > Size[child[x]]) {
            child[x] = g[x][i];
        }
    }
    if (Size[child[x]] * 2 > Size[x]) {
        int now = res[child[x]];
        while ((Size[x] - Size[now]) * 2 > Size[x]) {
            now = fa[now];
        }
        res[x] = now;
    } else {
        res[x] = x;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> q;
    for (int i = 2, x; i <= n; i++) {
        cin >> x;
        fa[i] = x;
        g[x].push_back(i);
    }
    dfs(1);
    while (q--) {
        int x;
        cin >> x;
        cout << res[x] << endl;
    }
    return 0;
}

C - Fools and Roads

用树上差分来统计，(u)走向(v)，则(u)、(v)之间的路径上的边权都加(1)，用差分数组表示就是(diff[u]+1, diff[v]+1, diff[lca(u,v)]-2)。
注意以点代边的思想。

#include <iostream>
using namespace std;

struct Edge {
    int v, next;
} edge[200010];
struct Line {
    int x, y;
} line[100010];
int cnt, head[100010], depth[100010], fa[100010][25], diff[100010], n, m, ans[100010], id[100010];

void swap(int &x, int &y) {
    x ^= y;
    y ^= x;
    x ^= y;
}

void addEdge(int u, int v) {
    edge[++cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt;
}

void dfs(int u, int pre) {
    depth[u] = depth[pre] + 1;
    fa[u][0] = pre;
    for (int i = 1; (1 << i) <= depth[u]; ++i) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].v;
        if (v != pre) {
            dfs(v, u);
        }
    }
}

int lca(int u, int v) {
    if (depth[u] > depth[v]) {
        swap(u, v);
    }
    for (int i = 20; i >= 0; --i) {
        if (depth[u] <= depth[v] - (1 << i)) {
            v = fa[v][i];
        }
    }
    if (u == v) {
        return u;
    }
    for (int i = 20; i >= 0; --i) {
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i], v = fa[v][i];
        }
    }
    return fa[u][0];
}

void sum(int u) {
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].v;
        if (v != fa[u][0]) {
            sum(v);
            diff[u] += diff[v];
        }
    }
    ans[id[u]] = diff[u];
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i < n; ++i) {
        cin >> line[i].x >> line[i].y;
        addEdge(line[i].x, line[i].y);
        addEdge(line[i].y, line[i].x);
    }
    dfs(1, 0);
    for (int i = 1; i < n; ++i) {
        if (depth[line[i].x] > depth[line[i].y]) {
            id[line[i].x] = i;
        } else {
            id[line[i].y] = i;
        }
    }
    cin >> m;
    while (m--) {
        int x, y;
        cin >> x >> y;
        int Lca = lca(x, y);
        diff[x]++;
        diff[y]++;
        diff[Lca] -= 2;
    }
    sum(1);
    for (int i = 1; i < n; ++i) {
        cout << ans[i] << ' ';
    }
    return 0;
}

D - Apple Tree

(dfs)序的两个数组(in)，(out)记录某结点进入和出来的时间，则对于一个结点(u)，其子树中某一结点(v)满足(in_u < in_v < out_v < out_u)。
用树状数组存储各时间戳所对应的结点的状况，则(getSum(out_u) - getSum(in_u - 1))所得结果就是以(u)为根的子树的状况。
由于每次进入或者出来时间戳都会加一，所以树状数组的大小应为(2 imes n)。

#include <iostream>
using namespace std;

struct Edge {
    int v, next;
} edge[100010];
char s;
int x;
int in[100010], out[100010], sum[200010], tot;
int n, m, cnt, head[100010];
bool vis[100010];

void addEdge(int u, int v) {
    edge[++cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt;
}

int lowbit(int x) { return x & (-x); }

void dfs(int x) {
    in[x] = ++tot;
    for (int i = head[x]; i; i = edge[i].next) {
        dfs(edge[i].v);
    }
    out[x] = ++tot;
}

void update(int x, int add) {  // 树状数组更新
    while (x <= 2 * n) {
        sum[x] += add;
        x += lowbit(x);
    }
}

int getSum(int x) {
    int ans = 0;
    while (x > 0) {
        ans += sum[x];
        x -= lowbit(x);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
    }
    dfs(1);
    for (int i = 1; i <= n; ++i) {
        update(in[i], 1);
        vis[i] = 1;
    }
    cin >> m;
    while (m--) {
        cin >> s >> x;
        if (s == 'C') {
            if (vis[x]) {
                update(in[x], -1);
            } else {
                update(in[x], 1);
            }
            vis[x] ^= 1;
        }
        if (s == 'Q') {
            cout << getSum(out[x]) - getSum(in[x] - 1) << endl;
        }
    }
    return 0;
}

E - Max Flow

用树上差分来统计，点的差分与边的差分有所不同，对于(u)、(v)之间的路径上的点权都加(1)，用差分数组表示就是(diff[u]+1, diff[v]+1, diff[lca(u,v)]-1, diff[fa[lca(u,v)][0]]-1)。

#include <iostream>
using namespace std;

int head[50010], cnt;
struct Edge {
    int v, next;
} edge[100010];

void addEdge(int u, int v) {
    edge[++cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt;
}

int n, k, ans, fa[50010][25], depth[50010];
int diff[50010];

void dfs(int u, int pre) {
    depth[u] = depth[pre] + 1;
    for (int i = 1; (1 << i) <= depth[u]; ++i) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].v;
        if (v != pre) {
            fa[v][0] = u;
            dfs(v, u);
        }
    }
}

int lca(int u, int v) {
    if (depth[u] > depth[v]) {
        swap(u, v);
    }
    for (int i = 20; i >= 0; --i) {
        if (depth[u] <= depth[v] - (1 << i)) {
            v = fa[v][i];
        }
    }
    if (u == v) {
        return u;
    }
    for (int i = 20; i >= 0; --i) {
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i], v = fa[v][i];
        }
    }
    return fa[u][0];
}

void getSum(int u, int pre) {
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].v;
        if (v != pre) {
            getSum(v, u);
            diff[u] += diff[v];
        }
    }
    ans = max(ans, diff[u]);
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> k;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
        addEdge(v, u);
    }
    dfs(1, 0);
    for (int i = 0; i < k; i++) {
        int u, v;
        cin >> u >> v;
        int Lca = lca(u, v);
        diff[u]++;
        diff[v]++;
        diff[Lca]--;
        diff[fa[Lca][0]]--;
    }
    getSum(1, 0);
    cout << ans << endl;
    return 0;
}

F - Count Descendants

用(dfs)序，记录每一个点进入的时间(in_i)和出来的时间(out_i)，则对于一个结点(u)，其子树中某一结点(v)满足(in_u < in_v < out_v < out_u)。
由此，用(vector)维护相同深度下所有点的(in)（(dfs)时间戳是有序的，所以甚至不需要排序），然后每次二分查找(in_u)和(out_u)的位置并相减即可。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge {
    int v, next;
} edge[400010];
int cnt, head[200010];
int n, in[200010], out[200010], tot, depth[200010];
int t;

void addEdge(int u, int v) {
    edge[++cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt;
}

vector<int> vec[200010];

void dfs(int u) {
    in[u] = ++tot;
    vec[depth[u]].push_back(in[u]);
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].v;
        depth[v] = depth[u] + 1;
        dfs(v);
    }
    out[u] = ++tot;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 2, x; i <= n; ++i) {
        cin >> x;
        addEdge(x, i);
    }
    dfs(1);
    cin >> t;
    while (t--) {
        int u, d;
        cin >> u >> d;
        cout << lower_bound(vec[d].begin(), vec[d].end(), out[u]) - lower_bound(vec[d].begin(), vec[d].end(), in[u]) << endl;
    }
    return 0;
}

G - 信息传递

建立传递者和接收者的单向边，加边的同时判断是否成环，记录环的大小并更新最小值。

#include <iostream>
using namespace std;

int n, fa[200010], ans = 0x3f3f3f3f, cnt, x;

int get(int x) {
    cnt++;
    return fa[x] == x ? x : get(fa[x]);
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
    }
    for (int i = 1; i <= n; ++i) {
        cnt = 0;
        cin >> x;
        if (get(x) == i) {
            ans = min(ans, cnt);
        } else {
            fa[i] = x;
        }
    }
    cout << ans;
    return 0;
}

H - The Tag Game

(A)一直沿(A)、(B)之间的最短路径走，(B)则往深度更大的结点走。
所以求出刚开始(A)、(B)之间的路径，找到此路径上(B)能在(A)之前到达且深度最大的结点(C)，则(ans =( 1到C的距离+C与其子树中深度最大的叶子结点之间的距离)*2)。

#include <cstring>
#include <iostream>
using namespace std;

int n, x, step, d[200010], path[200010], vis[200010], depth[200010];
int cnt, head[200010];
struct Edge {
    int v, next;
} edge[400010];

void addEdge(int u, int v) {
    edge[++cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt;
}

int dfs(int u, int fa) {  // 求深度
    int maxn = 0;
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].v;
        if (v != fa) {
            depth[v] = depth[u] + 1;
            maxn = max(dfs(v, u), maxn);
        }
    }
    return d[u] = maxn + 1;
}

void find_path(int u, int fa, int k) {
    if (step) {
        return;
    }
    path[k] = u;
    if (u == x) {
        step = k;
        return;
    }
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].v;
        if (v != fa) {
            find_path(v, u, k + 1);
        }
    }
}

int main() {
    while (cin >> n >> x) {
        cnt = 0;
        memset(head, 0, sizeof(head));
        for (int i = 1, u, v; i < n; ++i) {
            cin >> u >> v;
            addEdge(u, v);
            addEdge(v, u);
        }
        int ans = 0;
        memset(d, 0, sizeof(d));
        memset(vis, 0, sizeof(vis));
        step = 0, depth[1] = 1;
        dfs(1, 0);
        find_path(1, 0, 1);
        for (int i = step, j = 1; i && !vis[i]; --i, ++j) {
            vis[j] = 1;
            if (!vis[i]) {
                ans = max(ans, d[path[i]] - 1 + depth[path[i]] - 1);
            }
        }
        cout << ans * 2 << endl;
    }
    return 0;
}

相关推荐