猫先生头条

P3320 [SDOI2015] 寻宝游戏 与 P10930 异象石 与 CF176E Archaeology

2024-08-30 14:17 由 rgw2010 发表于 #后端开发

思路：

考虑按照 dfn 序将关键点的集合排序后为 \(a_0,a_1,\cdots,a_k\)，则答案为：

\[\frac{\sum\limits_{i=0}^k \operatorname{dis}(a_i,a_{(i+1) \bmod k})}{2} \]

简单证明一下：

需要找出包含一些关键点的最小联通导出子图。

则随便以一个关键点为根，对于子树内没有关键点的子树直接丢掉，就形成了新树；新树的叶子节点绝对都是关键点。

我们要找出新树的边集数量，即在 dfs 搜索的时候，每条边会在搜入子树时经过一次，出子树的时候经过一次，总计每条边会经过两次。

这个 dfs 搜索的过程等价于按照叶子节点 dfn 序的相邻取距离。

故我们需要动态维护上面那个式子的答案，注意到每次我们只删除或插入一个数，直接使用 set 维护即可。

如果你想，也自己写平衡树。

时间复杂度为 \(O(Q \log N)\)。

P10930 异象石 与 CF176E Archaeology Code： 
#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(int i=l;i<=r;i++)
#define _For(i,l,r) for(int i=r;i>=l;i--)
using namespace std;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=1e5+10;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
inline char get(){
    char c;
    while(1){
        c=getchar();
        if(c=='+'||c=='-'||c=='?')
          break;
    }
    return c;
}
char op;
ll n,m,u,v,w,x,ans,cnt;
ll dfn[N];
set<pi> S;
vector<pi> E[N];
void add(ll u,ll v,ll w){
    E[u].push_back({v,w});
    E[v].push_back({u,w});
}
void dfs(ll u,ll fa){
    dfn[u]=++cnt;
    for(auto t:E[u]){
        ll v=t.fi;
        if(v==fa)
          continue;
        dfs(v,u);
    }
}
namespace Tree{
    ll siz[N],z[N],fa[N],t[N],d[N],dep[N];
    void dfs1(ll u,ll f){
        siz[u]=1;
        for(auto t:E[u]){
            ll v=t.fi,w=t.se;
            if(v==f)
              continue;
            fa[v]=u;
            d[v]=d[u]+w;
            dep[v]=dep[u]+1;
            dfs1(v,u);
            siz[u]+=siz[v];
            if(siz[v]>siz[z[u]])
              z[u]=v;
        }
    }
    void dfs2(ll u,ll k){
        t[u]=k;
        if(!z[u])
          return ;
        dfs2(z[u],k);
        for(auto t:E[u]){
            ll v=t.fi;
            if(v==fa[u]||v==z[u])
              continue;
            dfs2(v,v);
        }
    }
    ll Lca(ll u,ll v){
        while(t[u]!=t[v]){
            if(dep[t[u]]<dep[t[v]])
              swap(u,v);
            u=fa[t[u]];
        }
        return dep[u]<dep[v]?u:v;
    }
    ll dis(ll u,ll v){
        return d[u]+d[v]-2ll*d[Lca(u,v)];
    }
    void init(){
        dfs1(1,1);
        dfs2(1,1);
    }
};
void insert(ll x){
    if(S.empty()){
        S.insert({dfn[x],x});
        return ;
    }
    set<pi>::iterator a,b;
    b=S.upper_bound({dfn[x],x});
    if(b==S.end()){
        a=b,a--;
        ans-=Tree::dis((*S.begin()).se,(*a).se);
        ans+=Tree::dis((*S.begin()).se,x);
        ans+=Tree::dis((*a).se,x);
    }
    else if(b==S.begin()){
        a=S.end(),a--;
        ans-=Tree::dis((*b).se,(*a).se);
        ans+=Tree::dis(x,(*a).se);
        ans+=Tree::dis(x,(*b).se);
    }
    else{
        a=b,a--;
        ans-=Tree::dis((*a).se,(*b).se);
        ans+=Tree::dis(x,(*a).se);
        ans+=Tree::dis(x,(*b).se);
    }
    S.insert({dfn[x],x});
}
void del(ll x){
    if(S.size()==1){
        S.erase({dfn[x],x});
        return ;
    }
    set<pi>::iterator a,b,c,d=S.end();
    a=b=c=S.find({dfn[x],x});
    a--,d--,c++;
    if(c!=S.end())
      ans-=Tree::dis((*c).se,(*b).se);
    if(b!=S.begin())
      ans-=Tree::dis((*a).se,(*b).se);
    if(c!=S.end()&&b!=S.begin())
      ans+=Tree::dis((*a).se,(*c).se);
    if(b==S.begin()){
        ans-=Tree::dis((*b).se,(*d).se);
        ans+=Tree::dis((*c).se,(*d).se);
    }
    if(c==S.end()){
        ans-=Tree::dis((*b).se,(*S.begin()).se);
        ans+=Tree::dis((*a).se,(*S.begin()).se);
    }
    S.erase(b);
}
int main(){
    n=read();
    For(i,1,n-1){
        u=read(),v=read(),w=read();
        add(u,v,w);
    }
    dfs(1,1);
    Tree::init();
    m=read();
    while(m--){
        op=get();
        if(op=='+'){
        	x=read();
        	insert(x);
		}
        else if(op=='-'){
        	x=read();
        	del(x);
		}
        else{
            write(ans>>1);
            putchar('\n');
        }
        //cerr<<(ans>>1)<<'\n';
//        cerr<<"Yes";
    }
    return 0;
}
P3320 [SDOI2015] 寻宝游戏 Code： 
#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(int i=l;i<=r;i++)
#define _For(i,l,r) for(int i=r;i>=l;i--)
using namespace std;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=1e5+10;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
inline char get(){
    char c;
    while(1){
        c=getchar();
        if(c=='+'||c=='-'||c=='?')
          break;
    }
    return c;
}
char op;
ll n,m,u,v,w,x,ans,cnt;
ll dfn[N];
set<pi> S;
vector<pi> E[N];
bool f[N];
void add(ll u,ll v,ll w){
    E[u].push_back({v,w});
    E[v].push_back({u,w});
}
void dfs(ll u,ll fa){
    dfn[u]=++cnt;
    for(auto t:E[u]){
        ll v=t.fi;
        if(v==fa)
          continue;
        dfs(v,u);
    }
}
namespace Tree{
    ll siz[N],z[N],fa[N],t[N],d[N],dep[N];
    void dfs1(ll u,ll f){
        siz[u]=1;
        for(auto t:E[u]){
            ll v=t.fi,w=t.se;
            if(v==f)
              continue;
            fa[v]=u;
            d[v]=d[u]+w;
            dep[v]=dep[u]+1;
            dfs1(v,u);
            siz[u]+=siz[v];
            if(siz[v]>siz[z[u]])
              z[u]=v;
        }
    }
    void dfs2(ll u,ll k){
        t[u]=k;
        if(!z[u])
          return ;
        dfs2(z[u],k);
        for(auto t:E[u]){
            ll v=t.fi;
            if(v==fa[u]||v==z[u])
              continue;
            dfs2(v,v);
        }
    }
    ll Lca(ll u,ll v){
        while(t[u]!=t[v]){
            if(dep[t[u]]<dep[t[v]])
              swap(u,v);
            u=fa[t[u]];
        }
        return dep[u]<dep[v]?u:v;
    }
    ll dis(ll u,ll v){
        return d[u]+d[v]-2ll*d[Lca(u,v)];
    }
    void init(){
        dfs1(1,1);
        dfs2(1,1);
    }
};
void insert(ll x){
    if(S.empty()){
        S.insert({dfn[x],x});
        return ;
    }
    set<pi>::iterator a,b;
    b=S.upper_bound({dfn[x],x});
    if(b==S.end()){
        a=b,a--;
        ans-=Tree::dis((*S.begin()).se,(*a).se);
        ans+=Tree::dis((*S.begin()).se,x);
        ans+=Tree::dis((*a).se,x);
    }
    else if(b==S.begin()){
        a=S.end(),a--;
        ans-=Tree::dis((*b).se,(*a).se);
        ans+=Tree::dis(x,(*a).se);
        ans+=Tree::dis(x,(*b).se);
    }
    else{
        a=b,a--;
        ans-=Tree::dis((*a).se,(*b).se);
        ans+=Tree::dis(x,(*a).se);
        ans+=Tree::dis(x,(*b).se);
    }
    S.insert({dfn[x],x});
}
void del(ll x){
    if(S.size()==1){
        S.erase({dfn[x],x});
        return ;
    }
    set<pi>::iterator a,b,c,d=S.end();
    a=b=c=S.find({dfn[x],x});
    a--,d--,c++;
    if(c!=S.end())
      ans-=Tree::dis((*c).se,(*b).se);
    if(b!=S.begin())
      ans-=Tree::dis((*a).se,(*b).se);
    if(c!=S.end()&&b!=S.begin())
      ans+=Tree::dis((*a).se,(*c).se);
    if(b==S.begin()){
        ans-=Tree::dis((*b).se,(*d).se);
        ans+=Tree::dis((*c).se,(*d).se);
    }
    if(c==S.end()){
        ans-=Tree::dis((*b).se,(*S.begin()).se);
        ans+=Tree::dis((*a).se,(*S.begin()).se);
    }
    S.erase(b);
}
int main(){
    n=read(),m=read();
    For(i,1,n-1){
        u=read(),v=read(),w=read();
        add(u,v,w);
    }
    dfs(1,1);
    Tree::init();
    while(m--){
        x=read();
        if(f[x])
          del(x);
        else
          insert(x);
        f[x]^=1ll;
        write(ans);
        putchar('\n');
    }
    return 0;
}