JZOJ5918【NOIP2018模拟10.20】Car

题目

在这里插入图片描述
最近比较懒,题目描述都直接截图了。

题目大意

给你一棵树,还有树上的几条路径,一条路径上的点到路径上其它任意点的代价为11。然后是一堆询问,问从一个点到另一个点的最小代价。


思路

一开始做这题时,就自然地往链剖或倍增方面想。
链剖想不出,于是就想倍增。
对于每个点,预处理出它花11的代价能到达的最远祖先。
然后倍增一下~
询问的时候,就将两个点的LCALCA求出,然后两个点往上跳,直到再跳就超过LCALCA为止。
所以问题就转化成了求两个点是否被一条路径直接连通,如果是,就加11,否则加22
想不出来……
最后只能打暴力:将一个点作为根,然后粗暴地处理……


正解

事实证明我前面所思考的是正确的。
对于这个问题,其实可以转化成:是否有一条路径的两个端点分别在这两个点的子树内……
好像是很显然的,可我为什么想不到……
于是我们就可以求出它们的dfndfn序,这就成了一个平面上的问题。
每一条路径可以看做一个点,每一个询问可以看作一个矩形,求这个矩形当中是否有点出现。
然后就是一个简单的扫描线和树状数组了。


代码

有一点需要补充一下:
有的同学反映,这题递归会爆栈,所以要打人工栈。
反正我是没有爆栈……
后来听说xzb大爷想出一个不用dfs求dfn序的方法。
首先,我们可以通过拓扑排序之类的自底向上递推求出它们的siz等信息。(这题比较良心,由于每个点的父亲编号小于它,所以直接从后往前扫就好了。)
然后自顶向下(可以用bfs,这题直接从前往后扫就好了),
对于每个点分两种情况:

  1. 它是父亲的第一个儿子。那么它的dfndfn即为父亲加一。
  2. 否则,就是父亲上一个儿子的dfndfn加它的sizsiz

然后就可以简单地求出dfndfn了。
正常的bfs中,上一个点就是父亲的上一个儿子。
不过这题不用bfs,直接记录就好了。
在此膜拜xzb

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 200000
#define M N
#define Q N
int n;
int last[N+1];
int siz[N+1],dfn[N+1];
int fa[N+1][19],dep[N+1];
inline void get_dfn(){//这是一种不需要dfs求dfn的方法,解释见上
	dfn[1]=1;
	for (int i=2;i<=n;++i){
		if (last[fa[i][0]])
			dfn[i]=dfn[last[fa[i][0]]]+siz[last[fa[i][0]]];
		else
			dfn[i]=dfn[fa[i][0]]+1;
		last[fa[i][0]]=i;
	}
}
inline int LCA(int u,int v){
	if (dep[u]<dep[v])
		swap(u,v);
	for (int k=dep[u]-dep[v],i=0;k;k>>=1,++i)
		if (k&1)
			u=fa[u][i];
	if (u==v)
		return u;
	for (int i=17;i>=0;--i)
		if (fa[u][i]!=fa[v][i]){
			u=fa[u][i];
			v=fa[v][i];
		}
	return fa[u][0];
}
int m;
int up[N+1][19],dep2[N+1];
struct Oper{
	int x,l,r;
	int ty;
	int num;
} o[M*2+Q*2+1];
int cnt;
bool cmp(const Oper &a,const Oper &b){
	return a.x<b.x || a.x==b.x && a.ty<b.ty;	
}
int t[N+1];
#define lowbit(x) ((x)&(-x))
inline void change(int x){
	do{
		t[x]++;
		x+=lowbit(x);
	}
	while (x<=n);
}
inline int query(int x){
	int res=0;
	while (x){
		res+=t[x];
		x-=lowbit(x);
	}
	return res;
}
int ans[Q+1],cha[Q+1];
int main(){
	freopen("car.in","r",stdin);
	freopen("car.out","w",stdout);
	scanf("%d",&n);
	for (int i=2;i<=n;++i){
		scanf("%d",&fa[i][0]);
		e[++ne]={i,last[fa[i][0]]};
		last[fa[i][0]]=e+ne;
	}
	for (int i=1;i<=n;++i)
		dep[i]=dep[fa[i][0]]+1;//因为题目说每个点父亲的编号一定小于它,所以直接递推就好,下同。
	for (int i=n;i>=1;--i)
		siz[fa[i][0]]+=++siz[i];
	get_dfn(1);
	for (int i=1;i<=17;++i)
		for (int j=1;j<=n;++j)
			fa[j][i]=fa[fa[j][i-1]][i-1];//倍增处理
	for (int i=1;i<=n;++i)
		up[i][0]=i;//up[i][j]表示花费2^j的代价最远能到达的祖先
	scanf("%d",&m);
	for (int i=1;i<=m;++i){
		int u,v;
		scanf("%d%d",&u,&v);
		if (dfn[u]>dfn[v])
			swap(u,v);
		//处理花费1代价能到达的最远祖先
		int lca=LCA(u,v);
		if (dep[lca]<dep[up[u][0]])
			up[u][0]=lca;
		if (dep[lca]<dep[up[v][0]])
			up[v][0]=lca;
		//加入操作列表中,相当于点(因为它有对称性,所以正着反着都加进去)
		o[++cnt]={dfn[u],dfn[v],dfn[v],0,0};
		o[++cnt]={dfn[v],dfn[u],dfn[u],0,0};
	}
	for (int i=n;i>=1;--i)
		if (dep[up[i][0]]<dep[up[fa[i][0]][0]])
			up[fa[i][0]][0]=up[i][0];//从底向上递推出每个点花费1代价到达的最远祖先
	for (int i=1;i<=18;++i)
		for (int j=1;j<=n;++j)
			up[j][i]=up[up[j][i-1]][i-1];
	int q;
	scanf("%d",&q);
	for (int i=1;i<=q;++i){
		int u,v;
		scanf("%d%d",&u,&v);
		if (u==v)
			continue;
		if (up[u][18]!=up[v][18]){//判断两个点是否可以互相到达(因为N=200000,2^18>N,所以这是它能到达的最远祖先,因为这是一棵树,所以如果可达到的最远祖先不一样,那么他们就不能互相到达)
			ans[i]=-1;
			continue;
		}
		int lca=LCA(u,v);
		if (lca==u || lca==v){//在同一条链上的情况
			if (lca==u)
				swap(u,v);
			for (int j=17;j>=0;--j)
				if (dep[up[u][j]]>dep[v])
					u=up[u][j],ans[i]+=1<<j;//跳到LCA下的最远点
			ans[i]++;
			continue;
		}
		for (int j=17;j>=0;--j)
			if (dep[up[u][j]]>dep[lca])
				u=up[u][j],ans[i]+=1<<j;//跳到LCA下的最远点,下同
		for (int j=17;j>=0;--j)
			if (dep[up[v][j]]>dep[lca])
				v=up[v][j],ans[i]+=1<<j;
		//加入操作
		o[++cnt]={dfn[u]-1,dfn[v],dfn[v]+siz[v]-1,1,i};
		o[++cnt]={dfn[u]+siz[u],dfn[v],dfn[v]+siz[v]-1,-1,i};
	}
	sort(o+1,o+cnt+1,cmp);
	for (int i=1;i<=cnt;++i)//扫描线求出二维数点问题
		if (o[i].ty==0)
			change(o[i].l);
		else if (o[i].ty==1)
			cha[o[i].num]=query(o[i].r)-query(o[i].l-1);
		else
			ans[o[i].num]+=((query(o[i].r)-query(o[i].l-1))-cha[o[i].num]?1:2);
	for (int i=1;i<=q;++i)
		printf("%d
",ans[i]);
	return 0;
}

总结

以后,看见有关树的题目,如果普通的倍增、链剖都做不出来,就得要往dfndfn序方面想……

原文地址:https://www.cnblogs.com/jz-597/p/11145263.html