HNOI 2016 树
程序员文章站
2024-03-02 23:04:40
...
树
解读题意
1.有n个点的模板树
2.每次把模板树上a为根的子树接到大树的b下面
3.求两个点在大树上的距离
切分
P30暴力模拟:
1.全部连边
2.求lca
正解流程
1.对于那么多个接子树操作,显然不能全部接到大树上,那么试着接点别的代替
2.只把子树的根接到大树上
3.为了能求距离,接上去的边权应为两个结点在大树上的距离
4.对于序号的映射,就是在模板树上求区间第K值
具体操作
1.预处理模板树的主席树
2.建边(用主席树找到(大树)b点在模板树上的序号,(大树)b点对应的(大树的)结点序号,求出的dis+1就是新边权),新结点编号是总点数+1。
3.大树点的序号=大树上对应结点编号-1+模板树上第K大
4.对于每个询问,如果在同一结点上,直接映射到模板树上求lca;不在一个结点上,先求出其到(大树)结点的距离,在求大树上两个结点的距离
代码如下
#include<bits/stdc++.h>
using namespace std;
const int M=500005;
int n,m,Q;
int TD[M],To[M];
long long ID[M];
vector<int>E[M];
int head[M],asdf;
struct edge {
int to,nxt,cost;
} G[M*2];
void add_edge(int a,int b,int c) {
G[++asdf].to=b;
G[asdf].nxt=head[a];
G[asdf].cost=c;
head[a]=asdf;
}
int tot,Ls[M*20],Rs[M*20],sum[M*20],root[M];
void build(int &rt,int L,int R) {
rt=++tot;
sum[rt]=0;
if(L==R)return;
int mid=L+R>>1;
build(Ls[rt],L,mid);
build(Rs[rt],mid+1,R);
}
void update(int &rt,int pr,int x,int L,int R) {
rt=++tot;
sum[rt]=sum[pr]+1;
Ls[rt]=Ls[pr],Rs[rt]=Rs[pr];
if(L==R)return;
int mid=L+R>>1;
if(x<=mid)update(Ls[rt],Ls[pr],x,L,mid);
else update(Rs[rt],Rs[pr],x,mid+1,R);
}
int query(int rt,int pr,int K,int L,int R) {
if(L==R)return L;
int mid=L+R>>1;
if(sum[Ls[rt]]-sum[Ls[pr]]>=K)return query(Ls[rt],Ls[pr],K,L,mid);
else return query(Rs[rt],Rs[pr],K-sum[Ls[rt]]+sum[Ls[pr]],mid+1,R);
}
int fa[M][20],DEP[M];
long long dis[M];
int par[M][20],dfn[M],dep[M],dR[M],tid[M],siz[M];
void dfsI(int x,int f) {
siz[x]=1;
dfn[x]=++tot;
par[x][0]=f;
dep[x]=dep[f]+1;
tid[tot]=x;
for(int i=0; i<E[x].size(); i++) {
int y=E[x][i];
if(y==f)continue;
dfsI(y,x);
siz[x]+=siz[y];
}
dR[x]=tot;
}
void dfsII(int x,int f) {
fa[x][0]=f;
DEP[x]=DEP[f]+1;
for(int i=head[x]; i; i=G[i].nxt) {
int y=G[i].to;
if(y==f)continue;
dis[y]=dis[x]+G[i].cost;
dfsII(y,x);
}
}
int lca(int a,int b) {
if(dep[a]>dep[b])swap(a,b);
int tmp=dep[b]-dep[a];
for(int i=0; i<20; i++) {
if(tmp&1)b=par[b][i];
tmp>>=1;
}
if(a==b)return a;
for(int i=19; i>=0; i--) {
if(par[a][i]!=par[b][i]) {
a=par[a][i];
b=par[b][i];
}
}
return par[a][0];
}
int Dep(int a,int b) {
return dep[a]+dep[b]-2*dep[lca(a,b)];
}
int LCA(int a,int b) {
if(DEP[a]>DEP[b])swap(a,b);
int tmp=DEP[b]-DEP[a];
for(int i=0; i<20; i++) {
if(tmp&1)b=fa[b][i];
tmp>>=1;
}
if(a==b)return a;
for(int i=19; i>=0; i--) {
if(fa[a][i]!=fa[b][i]) {
a=fa[a][i];
b=fa[b][i];
}
}
return fa[a][0];
}
long long Dis(int a,int b) {
return dis[a]+dis[b]-2*dis[LCA(a,b)];
}
int find(int a,int b) {
int tmp=DEP[a]-DEP[b]-1;
for(int i=0; i<20; i++) {
if(tmp&1)a=fa[a][i];
tmp>>=1;
}
return a;
}
int main() {
scanf("%d %d %d",&n,&m,&Q);
int a,b;
for(int i=1; i<n; i++) {
scanf("%d %d",&a,&b);
E[a].push_back(b);
E[b].push_back(a);
}
//小树倍增
dfsI(1,0);
for(int i=1; i<20; i++) {
for(int j=1; j<=n; j++) {
par[j][i]=par[par[j][i-1]][i-1];
}
}
tot=0;
build(root[0],1,n);
for(int i=1; i<=n; i++) {
update(root[i],root[i-1],tid[i],1,n);
}
ID[1]=TD[1]=To[1]=1;
for(int i=1; i<=m; i++) {
long long b;
scanf("%d %lld",&a,&b);
int t=upper_bound(ID+1,ID+i+1,b)-ID-1;
b=query(root[dR[TD[t]]],root[dfn[TD[t]]-1],b-ID[t]+1,1,n);
int dd=Dep(TD[t],b);
add_edge(t,i+1,dd+1);
add_edge(i+1,t,dd+1);
To[i+1]=b;
ID[i+1]=ID[i]+siz[TD[i]];
TD[i+1]=a;
}
dfsII(1,0);
for(int i=1; i<20; i++) {
for(int j=1; j<=m+1; j++) {
fa[j][i]=fa[fa[j][i-1]][i-1];
}
}
for(int i=1; i<=Q; i++) {
long long a,b;
scanf("%lld %lld",&a,&b);
int t1=upper_bound(ID+1,ID+m+2,a)-ID-1;
int t2=upper_bound(ID+1,ID+m+2,b)-ID-1;
int x=query(root[dR[TD[t1]]],root[dfn[TD[t1]]-1],a-ID[t1]+1,1,n);
int y=query(root[dR[TD[t2]]],root[dfn[TD[t2]]-1],b-ID[t2]+1,1,n);
if(t1==t2) {
printf("%d\n",Dep(x,y));
} else {
int c=LCA(t1,t2);
long long ans=dis[t1]+dis[t2]-2*dis[c];
ans+=Dep(TD[t1],x);
ans+=Dep(TD[t2],y);
int xx,yy;
if(t1==c)xx=x;
else xx=To[find(t1,c)];
if(t2==c)yy=y;
else yy=To[find(t2,c)];
ans-=2*Dep(lca(xx,yy),TD[c]);
printf("%lld\n",ans);
}
}
return 0;
}