【CodeForces】983 E. NN country 树上倍增+二维数点

【题目】E. NN country
【题意】给定n个点的树和m条链，q次询问一条链(a,b)最少被多少条给定的链覆盖。\(n,m,q \leq 2*10^5\)。
【算法】树上倍增+二维数点（树状数组）
先从半链角度考虑。将每条给定链和每个询问拆成向上的一段和向下的一段。那么假设询问的半链最低端节点为x，贪心地选择x子树内向上延伸最远的给定半链（假设最高点为y），再从y继续贪心直至超过半链最顶端节点。再只考虑半链的前提下贪心显然正确。

但是我们注意到，这样贪心的复杂度是不正确的，因为如果每次只跳一条边的话复杂度就是链长了。树上跳点容易想到倍增，令\(f_{i,j}\)表示点\(i\)贪心跳\(2^j\)条链能到达的最高点，这样就可以直接倍增到最顶端节点了。注意不存在的点设为0。初始化\(f_{x,0}\)的过程可以用dfs实现，每个点比较自身出发的链的最高点和儿子子树出发的链的最高点。

接下来考虑全链。分别从两个端点倍增到最高的在lca之下的点处（需要特判一个点为另一个点的lca的情况），假设为x和y，那么接下来的问题就是判断x和y是否属于同一条链，如果是那么答案+1，否则答案+2。这实际上在询问是否有一条链的一个端点在x子树内，另一个端点在y子树内。进一步抽象成dfs序后，就是矩阵数点问题了，可以用扫描线（离线）+树状数组解决。注意数点要求有序点对，所以将所有链强制左端点的dfs序小。

复杂度\(O(n \ \ log \ \ n)\)。

#include
#include
#include
#define lowbit(x) (x&-x)
bool isdigit(char c){return c>='0'&&c<='9';}
int read(){
	int s=0,t=1;char c;
	while(!isdigit(c=getchar()))if(c=='-')t=-1;
	do{s=s*10+c-'0';}while(isdigit(c=getchar()));
	return s*t;
}	
using namespace std;
const int maxn=200010;
int n,deep[maxn],first[maxn],tot,f[maxn][22],fac[22],ans[maxn],in[maxn],ou[maxn],cnt,ask,c[maxn],ANS[maxn];
struct edge{int v,from;}e[maxn*2];
struct cyc{
	int x,y,k,id;
	bool operator < (const cyc &a)const{
		return x=1;i-=lowbit(i))ans+=c[i];return ans;}
namespace lca{
	int f[maxn][22];
	void dfs(int x,int fa){
		in[x]=++cnt;
		for(int j=1;(1<=0;j--)if((1<in[b])swap(a,b);//swap
		if(!f[a][0]||deep[t]in[y])swap(x,y);//
		for(int j=20;j>=0;j--)if(f[x][j]&&deep[f[x][j]]>deep[t])x=f[x][j],ans[i]+=fac[j];
		for(int j=20;j>=0;j--)if(f[y][j]&&deep[f[y][j]]>deep[t])y=f[y][j],ans[i]+=fac[j];
		if((!f[x][0]&&x!=t)||(!f[y][0]&&y!=t)){ans[i]=-1;continue;}
		if(x==t||y==t)ans[i]++;else{
			ans[i]+=2;
			d[++ask]=(cyc){ou[x],ou[y],1,i};
			d[++ask]=(cyc){in[x]-1,ou[y],-1,i};
			d[++ask]=(cyc){ou[x],in[y]-1,-1,i};
			d[++ask]=(cyc){in[x]-1,in[y]-1,1,i};
		}
		
	}
	sort(d+1,d+ask+1);
	for(int i=1;i<=ask;i++){
		if(!d[i].id){
			modify(d[i].y,d[i].k);
		}
		else{
			ANS[d[i].id]+=d[i].k*query(d[i].y);
		}
	}
	for(int i=1;i<=q;i++)printf("%d\n",ans[i]-(ANS[i]>0));
	return 0;
}