题目链接

https://www.acwing.com/problem/content/2729/

一些废话

做了好久，不过其实还是图论掌握程度还不够

一些思路

1. 利用给的边建一棵生成树，那么对于其余任意边，它们在图上相连一定有一个唯一环
2. 虽然本题说以首都为起点，以首都为终点，但是完全可以看作是从首都到首都的最大异或路径，参考这题（最大XOR路径 ）就发现本题其实就是弱智。弱智还做这么久
3. 对于边权的修改，思考线段树分治的特性，显然是对于这样的边，我们要给它划分一个新的时段。同时对于这条新边，不要忘记继承它原来的边的信息（第几次添加）

一些坑点

1. Q可能等于0 （不仔细看数据范围是这样的）
2. bitset的大小比较（或者说类的大小比较），这是语法问题，不过要查很多资料才能使用
3. 继承原来的边的信息

一些做法

通过并查集处理环的异或和

这种要按秩合并，且执行merge操作中，其边权不是简单 w ，而是 w ^ getdis(u) ^ getdis(v)
这是因为并查集的合并都是祖先节点的父亲数组的修改，所以此时的 边权 要从 u 和 v 改变成 find(u) 和 find(v)，因此是 w ^ getdis(u) ^ getdis(v)
代码如下：

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<vector>
#include<stack>
#include<map>
#include<cstring>
#include<queue>
#include<set>
#include<functional>
#include<assert.h>
#include<cmath>
#include<bitset>
#include<algorithm>
using namespace std;

const int maxn = 505;
using BS = bitset<1005>;

void print(BS res)
{
    int k = res.size() - 1;
    while(k > 0 && res[k] == 0) k--;
    for(int i = k; i >= 0; i--)
        cout << res[i];
    cout << "\n";
}


struct UFS
{
    int fa[maxn], rk[maxn];
    BS dis[maxn];
    stack<array<int, 2>> opst;

    void init(int n = maxn - 5)
    {
        for(int i = 1; i <= n; i++)
        {
            fa[i] = i;
            rk[i] = 0;
            dis[i].reset();
        }
    }

    int find(int x)
    {
        while(x != fa[x]) x = fa[x];
        return x;
    }

    void merge(int u, int v, BS w)
    {
        u = find(u), v = find(v);
        if(rk[u] > rk[v]) swap(u, v);
        opst.push({u, rk[v]});
        fa[u] = v; dis[u] = w;
        if(rk[u] == rk[v]) ++rk[v];
    }

    BS getdis(int x)
    {
        BS res; res.reset();
        while(x != fa[x]) res ^= dis[x], x = fa[x];
        return res;
    }

    void undo()
    {
        auto [u, rnk] = opst.top(); opst.pop();
        rk[fa[u]] = rnk;
        fa[u] = u; dis[u].reset();
    }
}ufs;

struct LinerBase
{
    vector<BS> base;

    LinerBase() {base = vector<BS>(1005); }

    void insert(BS x)
    {
        for(int i = 1000; i >= 0; i--)
        {
            if(!x.test(i)) continue;
            if(!base[i].any()) return base[i] = x, void();
            x ^= base[i];
        }
    }

    void getmax()
    {
        BS res; res.reset();
        for(int i = 1000; i >= 0; i--)
            if(!res.test(i)) 
                res ^= base[i];
        print(res);
    }

} ;


vector<int> nums[maxn << 3];
struct E
{
    int u, v;
    BS w;
}edge[maxn << 2];
int st[maxn << 2], ed[maxn << 2];
int match[maxn << 2];

int ls(int x) {return x << 1; }
int rs(int x) {return x << 1 | 1; }

void update(int rt, int l, int r, int nl, int nr, int id)
{
    if(nl <= l && r <= nr)
    {
        nums[rt].push_back(id);
        return ;
    }
    int mid = l + r >> 1;
    if(nl <= mid) update(ls(rt), l, mid, nl, nr, id);
    if(mid < nr) update(rs(rt), mid + 1, r, nl, nr, id);
}

void solve(int rt, int l, int r, LinerBase lb)
{
    for(auto id : nums[rt])
    {
        auto [u, v, w] = edge[id];
        BS res(w ^ ufs.getdis(u) ^ ufs.getdis(v));
        lb.insert(res);
    }
    if(l == r)
    {
        lb.getmax();
    }
    else 
    {
        int mid = l + r >> 1;
        solve(ls(rt), l, mid, lb);
        solve(rs(rt), mid + 1, r, lb);
    }
}



int main(int argc, char const *argv[])
{
#ifdef CHAYI
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
    clock_t c1 = clock();
#endif
    //==================================
    cin.tie(0)->sync_with_stdio(false);
    int n, m, q;
    cin >> n >> m >> q;
    ufs.init(n);
    LinerBase lb;
    for(int i = 1; i <= m; i++)
    {
        int u, v; string str;
        cin >> u >> v >> str;
        BS w(str);
        w ^= ufs.getdis(u) ^ ufs.getdis(v);
        if(ufs.find(u) == ufs.find(v)) lb.insert(w);
        else ufs.merge(u, v, w);
    }
    m = 0;
    int add_cnt = 0;
    for(int i = 1; i <= q; i++)
    {
        string opt, str;
        int u, v, k;
        cin >> opt;
        switch (opt[1])
        {
        case 'd':
            cin >> u >> v >> str;
            edge[++m] = {u, v, BS(str)};
            st[m] = i, ed[m] = q;
            match[++add_cnt] = m;
            break;
        case 'a':
            cin >> k;
            ed[match[k]] = i - 1;
            break;
        case 'h':
            cin >> k >> str;
            ed[match[k]] = i - 1;
            edge[++m] = {edge[match[k]].u, edge[match[k]].v, BS(str)};
            st[m] = i, ed[m] = q;
            match[k] = m;
        default:
            break;
        }
    }
    for(int i = 1; i <= m; i++)
        update(1, 0, q, st[i], ed[i], i);
    solve(1, 0, q, lb);
    //==================================
#ifdef CHAYI
    cerr << "Time used:" << clock() - c1 << "ms" << "\n";
#endif
    return 0;
}

建图以计算环的异或和

这个就很显然了，钦定从1出发，计算到每个点的异或路径，对于一个环，显然是 dis[u] ^ dis[v] ^ w
代码如下：

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<vector>
#include<stack>
#include<map>
#include<cstring>
#include<queue>
#include<set>
#include<functional>
#include<assert.h>
#include<cmath>
#include<bitset>
#include<algorithm>
using namespace std;

const int maxn = 1005;
using BS = bitset<maxn>;
struct UFS
{
    int fa[maxn], rk[maxn];
    stack<array<int, 2>> opst;

    void init(int n = maxn - 5)
    {
        for(int i = 1; i <= n; i++)
        {
            fa[i] = i;
            rk[i] = 0;
        }
    }

    int find(int x)
    {
        while(x != fa[x]) x = fa[x];
        return x;
    }

    void merge(int u, int v)
    {
        u = find(u), v = find(v);
        if(rk[u] > rk[v]) swap(u, v);
        opst.push({u, rk[v]});
        fa[u] = v;
        if(rk[u] == rk[v]) ++rk[v];
    }

    void undo()
    {
        auto [u, rnk] = opst.top(); opst.pop();
        rk[fa[u]] = rnk;
        fa[u] = u;
    }
}ufs;

void print(BS res)
{
    int k = res.size();
    while(k > 0 && res[k] == 0) --k;
    for(; k >= 0; k--)
        cout << res[k];
    cout << "\n";
}

struct LinerBase
{
    vector<BS> base;
    LinerBase() {base = vector<BS>(maxn); }

    void insert(BS x)
    {
        if(!x.any()) return ;
        int k = x.size(); while(x[k] == 0) --k;
        if(!base[k].any()) return base[k] = x, void();
        insert(base[k] ^ x);
    }

    void getmax()
    {
        BS res; res.reset();
        for(int i = 1000; i >= 0; i--)
        {
            if(!base[i].any()) continue;
            if(!res.test(i)) res ^= base[i];
        }
        print(res);
    }
} ;

struct E
{
    int to, nxt;
    BS w;
}graph[maxn << 1];
BS dis[maxn >> 1];
int head[maxn];
int tot;

void init(int n = maxn - 5)
{
    memset(head, -1, sizeof(head));
    int tot = 0;
    ufs.init(n);
}

void AddEdge(int u, int v, BS w)
{
    graph[tot] = {v, head[u], w};
    head[u] = tot++;
}

void dfs(int u, int fa)
{
    for(int i = head[u]; ~i; i = graph[i].nxt)
    {
        int v = graph[i].to;
        dis[v] = dis[u] ^ graph[i].w;
        if(v == fa) continue;
        dfs(v, u);
    }
}

struct E2
{
    int u, v;
    BS w;
} edge[maxn << 1];
int cnt;
int match[maxn << 1];
int st[maxn << 1], ed[maxn << 1];

vector<int> nums[maxn << 2];

int ls(int x) {return x << 1; }
int rs(int x) {return x << 1 | 1; }

void update(int rt, int l, int r, int nl, int nr, int id)
{
    if(nl <= l && r <= nr)
    {
        nums[rt].push_back(id);
        return ;
    }
    int mid = l + r >> 1;
    if(nl <= mid) update(ls(rt), l, mid, nl, nr, id);
    if(mid < nr) update(rs(rt), mid + 1, r, nl, nr, id);
}

void solve(int rt, int l, int r, LinerBase lb)
{
    for(auto id : nums[rt])
    {
        auto [u, v, w] = edge[id];
        lb.insert(dis[u] ^ dis[v] ^ w);
    }
    if(l == r)
    {
        lb.getmax();
    }
    else 
    {
        int mid = l + r >> 1;
        solve(ls(rt), l, mid, lb);
        solve(rs(rt), mid + 1, r, lb);
    }
}


int main(int argc, char const *argv[])
{
#ifdef CHAYI
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
    clock_t c1 = clock();
#endif
    //==================================
    cin.tie(0)->sync_with_stdio(false);
    int n, m, q;
    cin >> n >> m >> q;
    init(n);
    for(int i = 1; i <= m; i++)
    {
        int u, v; string str;
        cin >> u >> v >> str;
        if(ufs.find(u) == ufs.find(v)) 
        {
            edge[++cnt] = {u, v, BS(str)};
            st[cnt] = 0, ed[cnt] = q;
        }
        else
        {
            ufs.merge(u, v);
            AddEdge(u, v, BS(str));
            AddEdge(v, u, BS(str));
        }
    }
    dfs(1, 0);
    int add_cnt = 0;
    for(int i = 1; i <= q; i++)
    {
        string opt, str;
        int u, v, k;
        cin >> opt;
        switch (opt[1])
        {
        case 'd':
            cin >> u >> v >> str;
            edge[++cnt] = {u, v, BS(str)};
            st[cnt] = i, ed[cnt] = q;
            match[++add_cnt] = cnt;
            break;
        case 'a':
            cin >> k;
            ed[match[k]] = i - 1;
            break;
        case 'h':
            cin >> k >> str;
            ed[match[k]] = i - 1;
            edge[++cnt] = {edge[match[k]].u, edge[match[k]].v, BS(str)};
            st[cnt] = i, ed[cnt] = q;
            match[k] = cnt;
            break;
        default:
            break;
        }
    }
    for(int i = 1; i <= cnt; i++)
        update(1, 0, q, st[i], ed[i], i);
    LinerBase lb;
    solve(1, 0, q, lb);
    //==================================
#ifdef CHAYI
    cerr << "Time used:" << clock() - c1 << "ms" << "\n";
#endif
    return 0;
}