一、例题①：P4320 道路相遇
可能是因为把树封装了，倍增怎么写都超时。
不过倍增确实慢，树剖快好多。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#define ll long long
#define pr make_pair
#define pb push_back
//#define lc (p<<1)
//#define rc (p<<1|1)
using namespace std;
char buffer[100001],*S,*T;
inline char Get_Char()
{
if (S==T)
{
T=(S=buffer)+fread(buffer,1,100001,stdin);
if (S==T) return EOF;
}
return *S++;
}
inline int read()
{
char c;int re=0;
for(c=Get_Char();c<'0'||c>'9';c=Get_Char());
while(c>='0'&&c<='9') re=re*10+(c-'0'),c=Get_Char();
return re;
}
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e15;
const int mod=1e9+7;
const int maxn=4000100;
int dfn[maxn],low[maxn],st[maxn];
int cnt=0,tp=0,n,m,q,cntf;
int d[maxn],f[maxn],son[maxn],si[maxn];
int id[maxn],top[maxn];
struct Tree
{
int head[maxn],ver[maxn],nt[maxn];
int tot=1;
void add(int x,int y)
{
ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}
}yy,yf;
void dfs(int x)
{
dfn[x]=low[x]=++cnt;
st[++tp]=x;
for(int i=yy.head[x];i;i=yy.nt[i])
{
int y=yy.ver[i];
if(!dfn[y])
{
dfs(y);
low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x])
{
cntf++;
yf.add(cntf,x);
yf.add(x,cntf);
int z;
do
{
z=st[tp--];
yf.add(cntf,z);
yf.add(z,cntf);
}while(z!=y);
}
}
else low[x]=min(low[x],dfn[y]);
}
}
void dfs1(int x,int fa)
{
int max_son=0;
si[x]=1;
for(int i=yf.head[x];i;i=yf.nt[i])
{
int y=yf.ver[i];
if(y==fa) continue;
d[y]=d[x]+1;
f[y]=x;
dfs1(y,x);
si[x]+=si[y];
if(si[y]>max_son) max_son=si[y],son[x]=y;
}
}
void dfs2(int x,int t)
{
top[x]=t;
id[x]=++cnt;
if(!son[x]) return ;
dfs2(son[x],t);
for(int i=yf.head[x];i;i=yf.nt[i])
{
int y=yf.ver[i];
if(y!=son[x]&&y!=f[x])
dfs2(y,y);
}
}
int lca(int x,int y)
{
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]]) swap(x,y);
x=f[top[x]];
}
return id[x]>id[y]?y:x;
}
int main(void)
{
n=read(),m=read();
int x,y;
for(int i=1;i<=m;i++)
{
x=read(),y=read();
yy.add(x,y);
yy.add(y,x);
}
cntf=n;
dfs(1);
dfs1(1,0);
dfs2(1,1);
q=read();
for(int i=1;i<=q;i++)
{
x=read(),y=read();
int lc=lca(x,y);
printf("%d\n",(d[x]+d[y]-2*d[lc])/2+1);
}
return 0;
}
二、例题②：P4606 [SDOI2018]战略游戏
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#define ll long long
#define pr make_pair
#define pb push_back
//#define lc (p<<1)
//#define rc (p<<1|1)
using namespace std;
char buffer[100001],*S,*T;
inline char Get_Char()
{
if (S==T)
{
T=(S=buffer)+fread(buffer,1,100001,stdin);
if (S==T) return EOF;
}
return *S++;
}
inline int read()
{
char c;int re=0;
for(c=Get_Char();c<'0'||c>'9';c=Get_Char());
while(c>='0'&&c<='9') re=re*10+(c-'0'),c=Get_Char();
return re;
}
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e15;
const int mod=1e9+7;
const int maxn=400100;
int dfn[maxn],low[maxn],st[maxn],s[maxn];
int cnt=0,tp=0,n,m,q,cntf;
int d[maxn],f[maxn],son[maxn],si[maxn];
int id[maxn],top[maxn],dis[maxn];
struct Tree
{
int head[maxn],ver[maxn],nt[maxn];
int tot;
void add(int x,int y)
{
ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}
}yy,yf;
void init(int n)
{
for(int i=1;i<=n;i++)
dfn[i]=son[i]=yy.head[i]=yf.head[i]=0;
yy.tot=yf.tot=1;
cnt=tp=0;
}
void dfs(int x)
{
dfn[x]=low[x]=++cnt;
st[++tp]=x;
for(int i=yy.head[x];i;i=yy.nt[i])
{
int y=yy.ver[i];
if(!dfn[y])
{
dfs(y);
low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x])
{
cntf++;
yf.add(cntf,x);
yf.add(x,cntf);
int z;
do
{
z=st[tp--];
yf.add(cntf,z);
yf.add(z,cntf);
}while(z!=y);
}
}
else low[x]=min(low[x],dfn[y]);
}
}
void dfs1(int x,int fa)
{
int max_son=0;
si[x]=1;
for(int i=yf.head[x];i;i=yf.nt[i])
{
int y=yf.ver[i];
if(y==fa) continue;
d[y]=d[x]+1;
dis[y]=dis[x]+(y<=n);
f[y]=x;
dfs1(y,x);
si[x]+=si[y];
if(si[y]>max_son) max_son=si[y],son[x]=y;
}
}
void dfs2(int x,int t)
{
top[x]=t;
id[x]=++cnt;
if(!son[x]) return ;
dfs2(son[x],t);
for(int i=yf.head[x];i;i=yf.nt[i])
{
int y=yf.ver[i];
if(y!=son[x]&&y!=f[x])
dfs2(y,y);
}
}
bool cmp(const int a,const int b)
{
return id[a]<id[b];
}
int lca(int x,int y)
{
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]]) swap(x,y);
x=f[top[x]];
}
return id[x]>id[y]?y:x;
}
int main(void)
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
init(n*2);
int x,y;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
yy.add(x,y);
yy.add(y,x);
}
cntf=n;
dfs(1);
cnt=0;
dfs1(1,0);
dfs2(1,1);
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
int cnts;
scanf("%d",&cnts);
for(int i=1;i<=cnts;i++)
scanf("%d",&s[i]);
sort(s+1,s+cnts+1,cmp);
s[cnts+1]=s[1];
int ans=0;
for(int i=1;i<=cnts;i++)
ans+=dis[s[i]]+dis[s[i+1]]-2*dis[lca(s[i],s[i+1])];
ans=ans/2-cnts+(lca(s[1],s[cnts])<=n);
printf("%d\n",ans);
}
}
return 0;
}
三、例③：【CF Round #278】Tourists
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#define ll long long
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
using namespace std;
char buffer[100001],*S,*T;
inline char Get_Char()
{
if (S==T)
{
T=(S=buffer)+fread(buffer,1,100001,stdin);
if (S==T) return EOF;
}
return *S++;
}
inline int read()
{
char c;int re=0;
for(c=Get_Char();c<'0'||c>'9';c=Get_Char());
while(c>='0'&&c<='9') re=re*10+(c-'0'),c=Get_Char();
return re;
}
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e15;
const int mod=1e9+7;
const int maxn=400100;
int dfn[maxn],low[maxn],st[maxn],val[maxn];
int cnt1=0,cnt2=0,tp=0,n,m,q,cntf;
int d[maxn],f[maxn],son[maxn],si[maxn];
int rk[maxn],id[maxn],top[maxn];
multiset<int>se[maxn];
struct Tree
{
int head[maxn],ver[maxn],nt[maxn];
int tot;
void add(int x,int y)
{
ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}
}yy,yf;
void dfs(int x)
{
dfn[x]=low[x]=++cnt1;
st[++tp]=x;
for(int i=yy.head[x];i;i=yy.nt[i])
{
int y=yy.ver[i];
if(!dfn[y])
{
dfs(y);
low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x])
{
cntf++;
yf.add(cntf,x);
yf.add(x,cntf);
int z;
do
{
z=st[tp--];
yf.add(cntf,z);
yf.add(z,cntf);
}while(z!=y);
}
}
else low[x]=min(low[x],dfn[y]);
}
}
void dfs1(int x,int fa)
{
int max_son=0;
si[x]=1;
if(fa) se[fa].insert(val[x]);
for(int i=yf.head[x];i;i=yf.nt[i])
{
int y=yf.ver[i];
if(y==fa) continue;
d[y]=d[x]+1;
f[y]=x;
dfs1(y,x);
si[x]+=si[y];
if(si[y]>max_son) max_son=si[y],son[x]=y;
}
}
void dfs2(int x,int t)
{
top[x]=t;
id[x]=++cnt2;
rk[cnt2]=x;
if(!son[x]) return ;
dfs2(son[x],t);
for(int i=yf.head[x];i;i=yf.nt[i])
{
int y=yf.ver[i];
if(y!=son[x]&&y!=f[x])
dfs2(y,y);
}
}
struct node
{
int l,r;
int val;
}t[maxn<<2];
void pushup(int cnt)
{
t[cnt].val=min(t[lc].val,t[rc].val);
}
void build(int l,int r,int cnt)
{
t[cnt].l=l,t[cnt].r=r;
if(l==r)
{
t[cnt].val=(rk[l]<=n?val[rk[l]]:*(se[rk[l]].begin()));
return ;
}
int mid=(l+r)>>1;
build(l,mid,lc);
build(mid+1,r,rc);
pushup(cnt);
}
void change(int pos,int cnt,int val)
{
if(t[cnt].l==t[cnt].r)
{
t[cnt].val=val;
return ;
}
if(pos<=t[lc].r) change(pos,lc,val);
else change(pos,rc,val);
pushup(cnt);
}
int ask(int l,int r,int cnt)
{
if(l<=t[cnt].l&&t[cnt].r<=r)
return t[cnt].val;
int minn=inf;
if(l<=t[lc].r) minn=min(minn,ask(l,r,lc));
if(r>=t[rc].l) minn=min(minn,ask(l,r,rc));
return minn;
}
void change(int x,int now)
{
if(f[x])
{
se[f[x]].erase(se[f[x]].find(val[x]));
se[f[x]].insert(now);
change(id[f[x]],1,*se[f[x]].begin());
}
val[x]=now;
change(id[x],1,now);
}
int ask(int x,int y)
{
int minn=inf;
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]]) swap(x,y);
minn=min(minn,ask(id[top[x]],id[x],1));
x=f[top[x]];
}
if(id[x]>id[y]) swap(x,y);
minn=min(minn,ask(id[x],id[y],1));
if(x>n) minn=min(minn,val[f[x]]);
return minn;
}
int main(void)
{
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)
scanf("%d",&val[i]);
int x,y;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
yy.add(x,y);
yy.add(y,x);
}
cntf=n;
dfs(1);
dfs1(1,0);
dfs2(1,1);
build(1,cntf,1);
char op[10];
for(int i=1;i<=q;i++)
{
scanf("%s%d%d",op,&x,&y);
if(op[0]=='A')
printf("%d\n",ask(x,y));
else change(x,y);
}
return 0;
}
京公网安备 11010502036488号