P3320 [SDOI2015] 寻宝游戏 与 P10930 异象石 与 CF176E Archaeology
cnblogs 2024-08-30 14:39:00 阅读 51
讲解 P3320 [SDOI2015] 寻宝游戏 与 P10930 异象石 与 CF176E Archaeology。
首先根据树上路径并等虚树知识，求出答案的式子后使用最近公共祖先算法计算答案，使用 set 快速进行插入删除操作。
思路：
考虑按照 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 序的相邻取距离。
故我们需要动态维护上面那个式子的答案，注意到每次我们只删除或插入一个数，直接使用 <code>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;
}
声明
本文内容仅代表作者观点，或转载于其他网站，本站不以此文作为商业用途
如有涉及侵权，请联系本站进行删除
转载本站原创文章，请注明来源及作者。