题解 P5327 [ZJOI2019]语言

· · 题解

竟然没有轻重链剖分+序列差分扫描线+虚树的做法。

枚举每个点能到达的点。发现就是包含这个点所有的 s\rightarrow t 的并的点数再减去自己。

因为这些链都经过同一点，那么他们的并自然就是一棵连通子图（树）了。

先考虑如何求出包含该点的链。我们利用轻重链剖分将链划为 O(\log n) 个区间，然后变为在序列上一个区间中加入该链的信息。使用差分，直接扫描线。这个是 雨天的尾巴 里面的 tirck。

所以现在的任务是：

维护点集，支持插入、删除点（就是链的两端点 s,t），求集合中点形成的极小连通子树的点数 -1。

有趣的是，点数 -1 就是边数。那么这个就完全是 [SDOI2015]寻宝游戏 了。

我们将点按照 dfn 排序，看作一个环。答案就是所有相邻点之间的距离之和的一半。

这个可以用 set O(\log n) 轻松完成。不过插入的点可能有重复，所以还需要一个 multiset 辅助。

轻重链剖分共造成了 O(n\log n) 次上述操作，所以时间复杂度为 O(n\log ^2 n)。

#include<bits/stdc++.h>
#define x first
#define y second
#define ll long long
using namespace std;
struct node
{
    int x,nxt;
}a[200005];
int h[100005];
int cnt;
int size[100005],f[100005],d[100005],son[100005];
int top[100005],dfn[100005];
int dcnt;
vector<pair<int,bool> > q[100005];
pair<int,int> c[100005];
void add(int x,int y)
{
    a[++cnt].x=y;
    a[cnt].nxt=h[x];
    h[x]=cnt;
}
void dfs1(int x,int deep,int fa)
{
    size[x]=1,f[x]=fa,d[x]=deep;
    for(int i=h[x],y;i;i=a[i].nxt)
        if((y=a[i].x)!=fa)
        {
            dfs1(y,deep+1,x);
            size[x]+=size[y];
            if(size[son[x]]<=size[y])
                son[x]=y;
        }
}
void dfs2(int x,int t)
{
    top[x]=t;
    dfn[x]=++dcnt;
    if(!son[x]) return;
    dfs2(son[x],t);
    for(int i=h[x],y;i;i=a[i].nxt)
    {
        y=a[i].x;
        if(y==f[x]||y==son[x]) continue;
        dfs2(y,y);
    }
}
void add_ar(int l,int r,int x)
{
    q[l].push_back({x,1});
    q[r+1].push_back({x,0});
}
void add(int x,int y,int id)
{
    while(top[x]!=top[y])
    {
        if(d[top[x]]<d[top[y]]) swap(x,y);
        add_ar(dfn[top[x]],dfn[x],id);  
        x=f[top[x]];
    }
    if(d[x]>d[y]) swap(x,y);
    add_ar(dfn[x],dfn[y],id);
}
int asklca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(d[top[x]]<d[top[y]]) swap(x,y);
        x=f[top[x]];
        //cout<<x<<endl;
    }
    return d[x]<d[y]?x:y;
}
int asklen(int x,int y)
{
    return (!x||!y)?0:d[x]+d[y]-d[asklca(x,y)]*2;
}
struct node_set
{
    set<pair<int,int> > t;
    multiset<int> f;
    int sum;
    node_set()
    {
        t.insert({-2e9,0});
        t.insert({2e9,0});
    }
    int val(int x)
    {
        int w1=(--t.lower_bound({dfn[x],x}))->second,w2=t.upper_bound({dfn[x],x})->second;
        return asklen(w1,x)+asklen(w2,x)-asklen(w1,w2);
    }
    void insert(int x)
    {
        //cout<<"insert "<<x<<endl;
        if(f.find(x)==f.end())
            sum+=val(x),t.insert({dfn[x],x});
        f.insert(x);
    }
    void erase(int x)
    {
        //cout<<"erase "<<x<<endl;
        f.erase(f.find(x));
        if(f.find(x)==f.end())
            sum-=val(x),t.erase({dfn[x],x});
    }
    int ask()
    {
        return (sum+asklen((++t.begin())->second,(--(--t.end()))->second))/2;
    }
}t;
int main()
{
    int n,m,x,y,i,j;
    ll sum=0;
    scanf("%d%d",&n,&m);
    for(i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    dfs1(1,1,0),dfs2(1,1);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&c[i].x,&c[i].y);
        add(c[i].x,c[i].y,i);
    }
    for(i=1;i<=n;i++)
    {
        for(j=0;j<q[i].size();j++)
            if(q[i][j].second)
                t.insert(c[q[i][j].first].x),
                t.insert(c[q[i][j].first].y);
            else
                t.erase(c[q[i][j].first].x),
                t.erase(c[q[i][j].first].y);
        sum+=t.ask();
    }
    cout<<sum/2;
}