C++11(clang++ 3.9) 解法, 执行用时: 666ms, 内存消耗: 54636K, 提交时间: 2019-03-09 18:12:20
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
#define ll long long
using namespace std;
const int inf=0x3f3f3f3f;
template <typename T>
inline void _read(T& x){
char t=getchar();bool sign=true;
while(t<'0'||t>'9'){if(t=='-')sign=false;t=getchar();}
for(x=0;t>='0'&&t<='9';t=getchar())x=x*10+t-'0';
if(!sign)x=-x;
}
int n,m,q,tot,clk;
int dfn[100005];
int SIZE[5000005],ls[5000005],rs[5000005],root[100005],Root[100005];
int id[100005],R[100005];
void insert(int pre,int &p,int l,int r,int x){
p=++tot;SIZE[p]=SIZE[pre]+1;
if(l==r)return;
int mid=(l+r)>>1;
ls[p]=ls[pre];rs[p]=rs[pre];
if(x<=mid)insert(ls[pre],ls[p],l,mid,x);
else insert(rs[pre],rs[p],mid+1,r,x);
}
void insert(int id,int v){insert(Root[id-1],Root[id],1,n,v);/*cout<<"insert:"<<id<<" v:"<<v<<endl;*/}
int query(int pre,int p,int l,int r,int k){
if(l==r)return l;
int mid=(l+r)>>1;
if(SIZE[ls[p]]-SIZE[ls[pre]]>=k)return query(ls[pre],ls[p],l,mid,k);
else return query(rs[pre],rs[p],mid+1,r,k-(SIZE[ls[p]]-SIZE[ls[pre]]));
}
int query(int x,int y,int k){return query(Root[x-1],Root[y],1,n,k);}
struct line{
int from,to,len;
line(){}
line(int x,int y,int z){from=x;to=y;len=z;}
};
struct graph{
line edge[200005];
int last[100005],_next[200005];
int fa[100005][20],dep[100005];
ll dis[100005],size[100005];
int e,vistime;
void init(){
e=vistime=0;
memset(fa,0,sizeof(fa));
memset(last,0,sizeof(last));
memset(_next,0,sizeof(_next));
}
void add_edge(int x,int y,int z){
edge[++e]=line(x,y,z);
_next[e]=last[x];
last[x]=e;
}
void dfs(int x){
//cout<<"dfs:"<<x<<endl;
for(int i=1;i<=18;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=last[x];i;i=_next[i]){
int v=edge[i].to;
//cout<<"v:"<<v<<endl;
if(v==fa[x][0])continue;
fa[v][0]=x;dep[v]=dep[x]+1;dis[v]=dis[x]+edge[i].len;
dfs(v);
}
}
void dfs2(int x){
//cout<<"dfs2:"<<x<<endl;
size[x]=1;id[x]=++clk;insert(clk,x);
for(int i=last[x];i;i=_next[i]){
int v=edge[i].to;
//cout<<"v:"<<v<<endl;
if(v==fa[x][0])continue;
dfs2(v);
size[x]+=size[v];
}
R[x]=clk;
}
void go_up(int& x,int step){
for(int i=18;i>=0;i--){
if(step&(1<<i))x=fa[x][i];
}
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
go_up(x,dep[x]-dep[y]);
if(x==y)return x;
for(int i=18;i>=0;i--){
if(fa[x][i]!=fa[y][i]){
x=fa[x][i];y=fa[y][i];
}
}
return fa[x][0];
}
ll dist(int x,int y){
return dis[x]+dis[y]-2ll*dis[lca(x,y)];
}
int up(int x,int y){
go_up(x,dep[x]-dep[y]-1);
return x;
}
};
graph ori,newg;
ll sum=0,cnt[200005];
int from[100005];
int pos;
int getid(ll x){
return lower_bound(cnt+1,cnt+1+pos,x)-cnt;
}
void query(ll a,ll b){
int ida=getid(a),roota=root[ida],aa=query(id[roota],R[roota],a-cnt[ida-1]);
int idb=getid(b),rootb=root[idb],bb=query(id[rootb],R[rootb],b-cnt[idb-1]);
int lca=newg.lca(ida,idb);
if(ida==idb){
printf("%lld\n",ori.dist(aa,bb));
return;
}
ll res=newg.dist(ida,idb)+ori.dis[aa]-ori.dis[roota]+ori.dis[bb]-ori.dis[rootb];
if(ida==lca){
int frb=from[newg.up(idb,lca)];
res-=ori.dis[aa]+ori.dis[frb]-ori.dist(aa,frb)-2*ori.dis[roota];
}
else if(idb==lca){
int fra=from[newg.up(ida,lca)];
res-=ori.dis[bb]+ori.dis[fra]-ori.dist(bb,fra)-2*ori.dis[rootb];
}
else{
int fra=from[newg.up(ida,lca)];
int frb=from[newg.up(idb,lca)];
res-=ori.dis[fra]+ori.dis[frb]-ori.dist(fra,frb)-2*ori.dis[root[lca]];
}
printf("%lld\n",res);
}
int main(){
ori.init();
newg.init();
int i,j,k;
cin>>n>>m>>q;
for(i=1;i<n;i++){
int x,y;
_read(x);_read(y);
ori.add_edge(x,y,1);
ori.add_edge(y,x,1);
}
ori.dfs(1);
ori.dfs2(1);
sum=n;cnt[1]=n;root[1]=pos=1;
for(i=2;i<=m+1;i++){
ll x,y;
_read(x);_read(y);
int ID=getid(y),ROOT=root[ID];
root[i]=x;pos=i;from[i]=query(id[ROOT],R[ROOT],y-cnt[ID-1]);
newg.add_edge(i,ID,ori.dis[from[i]]-ori.dis[ROOT]+1);
newg.add_edge(ID,i,ori.dis[from[i]]-ori.dis[ROOT]+1);
sum+=ori.size[x];cnt[i]=sum;
}
newg.dfs(1);
for(i=1;i<=q;i++){
ll x,y;
_read(x);_read(y);
query(x,y);
}
}
C++14(g++5.4) 解法, 执行用时: 435ms, 内存消耗: 48580K, 提交时间: 2020-07-10 15:08:21
#include<cstdio>
#include<algorithm>
using namespace std;typedef long long ll;
const int N=1e5+10;int n;int m;int q;
int dfn[N];int nfd[N];int df;int siz[N];int cnt;//开全局变量方便主席树类访问
struct smtree
{
struct data{int v;int x;}e[2*N];int al[N];int ct;
inline void add(int u,int v){e[++ct]=(data){v,al[u]};al[u]=ct;}
ll d[N];bool book[N];int fa[22][N];//倍增板子
void dfs(int x)
{
for(int i=0;fa[i][x];i++){fa[i+1][x]=fa[i][fa[i][x]];}
book[x]=true;siz[x]=1;dfn[++df]=x;nfd[x]=df;
for(int i=al[x],v=e[i].v;i;i=e[i].x,v=e[i].v)
{if(!book[v]){fa[0][v]=x;d[v]=d[x]+1;dfs(v);siz[x]+=siz[v];}}
}
inline int lca(int u,int v)//lca板子
{
if(d[u]<d[v]){swap(u,v);}int del=d[u]-d[v];
for(int i=0;del;del>>=1,i++){if(del&1){u=fa[i][u];}}if(u==v){return u;}
for(int i=20;i>=0;i--){if(fa[i][u]!=fa[i][v]){u=fa[i][u];v=fa[i][v];}}
return fa[0][u];
}
inline ll cd(int u,int v)//求祖先的距离，O(1)
{ll ret=abs(d[u]-d[v]);return ret;}
inline ll cdlca(int u,int v,int r)//求lca和公共根的距离
{ll ret=d[lca(u,v)]-d[r];return ret;}
}st;
struct per_linetree//主席树类
{
int s[2][22*N];int val[22*N];int root[N];int cnt;
inline void cson(int p1,int p2,int tp)//静态区间第k大板子没啥好说的
{s[tp][p2]=++cnt;s[tp^1][p2]=s[tp^1][p1];}
inline void add(int p1,int p2,int l,int r,int pos)
{
val[p2]=val[p1]+1;if(r-l==1){return;}int mid=(l+r)/2;
if(pos<=mid){cson(p1,p2,0);add(s[0][p1],cnt,l,mid,pos);}
else {cson(p1,p2,1);add(s[1][p1],cnt,mid,r,pos);}
}
inline int kth(int p1,int p2,int l,int r,int rk)
{
if(r-l==1){return r;}int mid=(r+l)/2;int nv=val[s[0][p2]]-val[s[0][p1]];
if(rk<=nv){return kth(s[0][p1],s[0][p2],l,mid,rk);}
else {return kth(s[1][p1],s[1][p2],mid,r,rk-nv);}
}
inline int ckth(int l,int r,int rk){return kth(root[l],root[r],0,n,rk);}
inline void build()//对dfn建主席树
{
root[0]=++cnt;for(int i=1;i<=n;i++)
{root[i]=++cnt;add(root[i-1],root[i],0,n,dfn[i]);}
}
struct nod//用来存bn区间右端点的结构体
{
ll v;int root;int bn;
friend bool operator <(nod a,nod b){return a.v<b.v;}
}a[N];int ctt;//有序数组
inline void dtr(ll x,int& root,int& su,int& bu)//这里额外返回一个root，代表bn.root
{
nod p=*(lower_bound(a+1,a+ctt+1,(nod){x,0,0}));//先lower_bound
root=p.root;bu=p.bn;int rk=x+siz[root]-p.v;//写的是第k小板子，所以转一下排名
su=ckth(nfd[root]-1,nfd[root]+siz[root]-1,rk);//计算sn
}
inline void push_nod(int root,int bu)//插入一个新节点，保证数组的有序性
{a[ctt+1]=(nod){a[ctt].v+siz[root],root,bu};ctt++;}
}plt;
struct bigtree
{
struct data{int v;int x;ll val;}e[2*N];int al[N];int ct;
inline void add(int u,int v,ll val){e[++ct]=(data){v,al[u],val};al[u]=ct;}
bool book[N];int fa[22][N];int d[N];ll dis[N];int att[N];
void dfs(int x)//倍增板子没啥好说的
{
book[x]=true;for(int i=0;fa[i][x];i++){fa[i+1][x]=fa[i][fa[i][x]];}
for(int i=al[x],v=e[i].v;i;i=e[i].x,v=e[i].v)
{if(!book[v]){dis[v]=dis[x]+e[i].val;d[v]=d[x]+1;fa[0][v]=x;dfs(v);}}
}
inline int lca(int u,int v,int& snu,int& snv)//魔改后的lca，可以传回j1,j2
{
if(u==v){return u;}//大力特判u==v
if(d[u]<d[v]){swap(u,v);swap(snu,snv);}
int del=d[u]-d[v]-1;//这里u跳到和v差1就好
for(int i=0;del>0;del>>=1,i++){if(del&1){u=fa[i][u];}}
if(fa[0][u]==v){snu=att[u];return v;}else if(del!=-1){u=fa[0][u];}//如果不是祖先的话还要补回来
for(int i=20;i>=0;i--){if(fa[i][u]!=fa[i][v]){u=fa[i][u];v=fa[i][v];}}
snu=att[u];snv=att[v];return fa[0][u];//如果不是祖先的话直接取att属性就好
}
inline ll cd(int u,int v,int p){return dis[u]+dis[v]-2*dis[p];}//因为我们求了lca了，因此直接算就好
}bt;
inline ll cd(ll u,ll v)//正式的计算距离的函数
{
int r1;int sn1;int bn1;int j1;int r2;int sn2;int bn2;int j2;
plt.dtr(u,r1,sn1,bn1);plt.dtr(v,r2,sn2,bn2);j1=sn1;j2=sn2;//强行转二元组
int p=bt.lca(bn1,bn2,j1,j2);int r0=plt.a[p].root;//计算j1.j2,p
return st.cd(r1,sn1)+st.cd(r2,sn2)-2*st.cdlca(j1,j2,r0)+bt.cd(bn1,bn2,p);//按公式算就行了
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<n;i++)
{int u;int v;scanf("%d%d",&u,&v);st.add(u,v);st.add(v,u);}
st.dfs(1);plt.build();plt.push_nod(1,++cnt);//记得一开始大树是有一个点的
for(int i=1;i<=m;i++)
{
int x;ll to;scanf("%d%lld",&x,&to);
int root;int sn;int bn;plt.dtr(to,root,sn,bn);//强行转二元组
plt.push_nod(x,++cnt);bt.att[cnt]=sn;//插点
int val=st.cd(sn,root)+1;//计算边权
bt.add(bn,cnt,val);bt.add(cnt,bn,val);//连边
}bt.dfs(1);
for(int i=1;i<=q;i++)
{
ll u;ll v;scanf("%lld%lld",&u,&v);
printf("%lld\n",cd(u,v));//大力计算就好了
}return 0;//拜拜程序~
}
