湘潭邀请赛 2018 E From Tree to Graph

时间:2023-02-02 20:54:44

题意:

  给出一棵树以及m,a,b,x0,y0。之后加m条边{(x1,LCA(x1,y1)),(x2,LCA(x2,y2))...(xm,LCA(xm,ym))}。定义z = f(0)^f(1)^...^f(n-1),其中f(i)代表删掉点i的连通块数。则xi = (axi-1+byi-1+z)%n,yi = (bxi-1+ayi-1+z)%n。求xm和ym

题解:

  维护每个点的度数。初始的点的度数即为删掉该点后的连通块数。

  第i次加边(xi,LCA(xi,yi))中xi到LCA(xi,yi)的路径上的点(除xi和LCA(xi,yi)以外)度数减1。

  每个点的父节点只有一个,用并查集维护每个点的父亲节点到其分支是否被计算过。

湘潭邀请赛 2018 E From Tree to Graph湘潭邀请赛 2018 E From Tree to Graph
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 5005;
int n, m, a, b, x, y, z;
int u, v;
int tot;
int f[N], depth[N], fa[15][N], g[N];
int head[N], nxt[N<<1], to[N<<1];
int find(int x) {
    return x==f[x]?x:f[x]=find(f[x]);
}
void dfs(int u, int pre, int d) {
    fa[0][u] = pre;
    depth[u] = d;
    int cnt = 0;
    for(int i = head[u]; ~i; i = nxt[i]) {
        if(to[i] != pre) dfs(to[i], u, d+1);
        cnt++;
    }
    g[u] =cnt;
}
int main() {
    while(~scanf("%d%d%d%d%d%d", &n, &m, &a, &b, &x, &y)) {
        tot = z = 0;
        for(int i = 0; i <= n; i++) f[i] = i, head[i] = -1;
        for(int i = 0; i < n-1; i++) {
            scanf("%d%d", &u, &v);
            to[++tot] = v; nxt[tot] = head[u]; head[u] = tot;
            to[++tot] = u; nxt[tot] = head[v]; head[v] = tot;
        }
        dfs(0, 0, 0);
        for(int i = 0; i < 13; i++) 
            for(int j = 0; j < n; j++) 
                fa[i+1][j] = fa[i][fa[i][j]];
        for(int i = 0; i < n; i++) z ^= g[i];
        while(m--) {
            u = (a*x+b*y+z)%n;
            v = (a*y+b*x+z)%n;
            x = u; y = v;
            if(depth[u]<depth[v]) swap(u, v);
            int dep = depth[u]-depth[v];
            if(dep>0) {
                for(int i = 13; i >= 0; i--) {
                    if(dep&(1<<i)) u = fa[i][u];
                }
            }
            for(int i = 13; i >= 0; i--) {
                if(fa[i][u] != fa[i][v]) {
                    u = fa[i][u];
                    v = fa[i][v];
                }
            }
            if(u!=v) v = fa[0][v];
            u = find(x);
            while(depth[fa[0][u]]>depth[v]) {
                z ^= g[fa[0][u]];
                g[fa[0][u]]--;
                z ^= g[fa[0][u]];
                f[u] = fa[0][u];
                u = find(u);
            }
        }
        printf("%d %d\n", x, y);
    }
}
View Code