首页 > 代码库 > 603E

603E

2024-10-14 21:43:39   213人阅读

LCT维护MST+子树信息

看了好长时间题解

editorial

结论：像做最小生成树一样，当每个连通块都是偶数个点就停下来。

每次复杂度mlogm

口胡

首先我们发现奇数个点是不满足每个点度数为奇数，因为一条边贡献两个度数，所以度数一定是偶数，但是奇数个点每个点奇数度度数总和是奇数，所以点数一定是偶数。

但是这样不足以解决问题。于是我们转化一下，如果一个连通块有偶数个点，那么这个连通块一定能满足条件。这里要注意，是满足条件，但是我们维护的东西并不满足条件。我们只维护最小生成森林，这样是不保证度数是奇数的，但是如果在森林上删去一些边，肯定能满足。既然多出来了一些边，怎么查找答案呢？我们每次加边，如果两个顶点不连通，那么我们连接，同时统计奇数个顶点的连通块，如果联通，那么我们删去形成的环上最大的边。然后把插入的边放进set里。每次查找，我们按边权从大到小检查，看这条边能否删去，能删去的条件是删掉这条边后两个连通块的点数都为偶数。删到不能删停下来。如果删掉一条边分裂成两个奇数大小的连通块，那么肯定是不满足条件的。这里就是解法的巧妙所在，我们保留一些可能没用的边，也不在乎性质，只有删边的时候才考虑。

然后还要维护子树信息。lct一般只能维护链上信息，但是我们发现，只有access和link和cut会改变子树之间的关系，那么我们就在这两个时候维护点权。（这里不是很清楚）

每次查询size的时候就把这个点转到根，查询即可。

好久没写lct都快忘了

#include<bits/stdc++.h>
using namespace std;
const int N = 600010;
struct edge {
    int u, v, w, id;
    edge(int u = 0, int v = 0, int w = 0, int id = 0) : u(u), v(v), w(w), id(id) { }
    bool operator < (edge e) const
    {
        return w == e.w ? id < e.id : w > e.w;
    }
};
vector<edge> ed;
set<edge> s;
int n, m, o;
namespace lct
{
    int top;
    int fa[N], child[N][2], size[N], v[N], tag[N], st[N], mx[N], id[N];
    bool isroot(int x) { return !fa[x] || (child[fa[x]][0] != x && child[fa[x]][1] != x); }
    void update(int x)
    {
        size[x] = size[child[x][0]] + size[child[x][1]] + v[x];
        mx[x] = id[x];
        if(ed[mx[child[x][0]]].w > ed[mx[x]].w) mx[x] = mx[child[x][0]];
        if(ed[mx[child[x][1]]].w > ed[mx[x]].w) mx[x] = mx[child[x][1]];
    }
    void pushdown(int x)
    {
        if(!tag[x]) return;
        tag[child[x][0]] ^= 1;
        tag[child[x][1]] ^= 1;
        swap(child[x][0], child[x][1]);
        tag[x] ^= 1;
    }
    void zig(int x)
    {
        int y = fa[x];
        fa[x] = fa[y];
        if(!isroot(y)) child[fa[x]][child[fa[x]][1] == y] = x;
        child[y][0] = child[x][1];
        fa[child[x][1]] = y;
        fa[y] = x;
        child[x][1] = y;
        update(y);
        update(x);
    }
    void zag(int x)
    {
        int y = fa[x];
        fa[x] = fa[y];
        if(!isroot(y)) child[fa[x]][child[fa[x]][1] == y] = x;
        child[y][1] = child[x][0];
        fa[child[x][0]] = y;
        fa[y] = x;
        child[x][0] = y;
        update(y);
        update(x);
    }
    void splay(int x)    
    {
        top = 0;
        st[++top] = x;
        for(int now = x; !isroot(now); now = fa[now]) st[++top] = fa[now];
        for(int i = top; i; --i) pushdown(st[i]);
        while(!isroot(x))
        {
            int y = fa[x], z = fa[y];
            if(isroot(y))
            {
                child[y][0] == x ? zig(x) : zag(x);
                break;
            }
            else if(child[y][0] == x && child[z][0] == y) { zig(y); zig(x); }
            else if(child[y][1] == x && child[z][1] == y) { zag(y); zag(x); }
            else if(child[y][1] == x && child[z][0] == y) { zag(x); zig(x); }
            else if(child[y][0] == x && child[z][1] == y) { zig(x); zag(x); }    
        }
    }
    void access(int x)
    {
        for(int y = 0; x; y = x, x = fa[x])
        {
            splay(x);
            v[x] -= size[y];
            v[x] += size[child[x][1]];
            child[x][1] = y;
            update(x);
        } 
    }
    void rever(int x)
    {
        access(x);
        splay(x);
        tag[x] ^= 1; //x本来是最深的，反转深度 
    }
    void link(int x, int y)
    {
        rever(x); 
        fa[x] = y;
        v[y] += size[x];
    }
    void cut(int x, int y)
    {
        rever(x); //u是最浅的 
        access(y);
        splay(y);
        fa[x] = child[y][0] = 0;
        v[y] -= size[x];
        update(y);
    }
    int find(int x)
    {
        access(x);
        splay(x);
        while(child[x][0]) x = child[x][0];
        return x;
    }
    int q(int x)
    {
        rever(x);
        return size[x];
    }
} using namespace lct;
void add_edge(edge e)
{
    if(q(e.u) & 1 && q(e.v) & 1) o -= 2;
    id[e.id + n] = e.id;
    mx[e.id + n] = e.id;
    link(e.u, e.id + n);
    link(e.v, e.id + n);
}
int delete_edge(edge e)
{
    cut(e.u, e.id + n);
    cut(e.v, e.id + n);
    if(q(e.u) & 1 && q(e.v) & 1) o += 2;
    return !(q(e.u) & 1);
}
int max_cost()
{
    if(o) return -1;
    while(delete_edge(*s.begin())) s.erase(*s.begin());
    add_edge(*s.begin());
    return (*s.begin()).w;
}
int find_max(int u, int v)
{
    rever(u);
    access(v);
    splay(v);
    return mx[v];
}
void new_edge(edge e)
{
    e.id = ed.size();
    ed.push_back(e);
    if(find(e.u) == find(e.v))
    {
        int id = find_max(e.u, e.v);
        if(ed[id].w <= e.w)    return;
        delete_edge(ed[id]);
    }
    add_edge(e);
    s.insert(e);
}
int main()
{
    scanf("%d%d", &n, &m);
    o = n;
    ed.push_back(edge(0, 0, 0, 0));
    for(int i = 1; i <= n; ++i) v[i] = 1;
    for(int i = 1; i <= m; ++i) 
    {
        edge e;
        scanf("%d%d%d", &e.u, &e.v, &e.w);
        new_edge(e);
        printf("%d\n", max_cost());
    }    
    return 0;
}

 

603E


联系
我们