天天看點
傳回

Luogu P1600 天天愛跑步

題面不好化簡。

規定

% 　　為了友善，先欽定一個點為根節點，這裡用1号點，并且規定一些符号。

　　 W u : W_u: Wu​:點 u u u 的觀測時間。

　　 l c a ( A , B ) : lca(A,B): lca(A,B): 點 A A A 和點 B B B 的最近公共祖先。

　　 A → B : A\rightarrow B: A→B: 點 A A A 到點 B B B 的（樹上唯一）路徑。

　　 F u : F_u: Fu​: 點 u u u 的父親。

　　 d e p u : dep_u: depu​: 點 u u u 的深度。

　　 a n s u : ans_u: ansu​: 點 u u u 最終的答案。

　　 d i s ( A , B ) : dis(A,B): dis(A,B): A → B A\rightarrow B A→B 的路徑長度。

　　鍊：深度嚴格遞增或遞減的路徑。

題解

% 　　可以發現，對于一個點，如果要考慮所有邊對其貢獻會非常困難。是以我們開始考慮對于每條邊，求出對路徑上的點的貢獻。我們首先把一條 S → T S\rightarrow T S→T 的路徑拆開，拆成 S → l c a ( S , T ) → T S\rightarrow lca(S,T)\rightarrow T S→lca(S,T)→T ，進一步拆開變成 S → l c a ( S , T ) S\rightarrow lca(S,T) S→lca(S,T) 和 l c a ( S , T ) → T lca(S,T)\rightarrow T lca(S,T)→T，然後分别考慮這兩部分對答案的貢獻，最後減去計算重複的 l c a ( S , T ) lca(S,T) lca(S,T)。

向上的鍊

% 　　先來考慮 S → l c a ( S , T ) S\rightarrow lca(S,T) S→lca(S,T)，根據題意，點 u u u 能觀測到這條路徑當且僅當點 u u u 在 S → l c a ( S , T ) S\rightarrow lca(S,T) S→lca(S,T) 上，且 W u = d e p S − d e p u W_u=dep_S-dep_u Wu​=depS​−depu​，即當花費 W u W_u Wu​ 的時間後恰好到達點 u u u，移項，得 d e p S = d e p u + W u dep_S=dep_u+W_u depS​=depu​+Wu​

% 　　換言之，對于點 u u u，所有對 a n s u ans_u ansu​ 産生貢獻的鍊 S → l c a ( S , T ) S\rightarrow lca(S,T) S→lca(S,T) 必須同時滿足以下三點。

  1. d e p S = d e p u + W u dep_S=dep_u+W_u depS​=depu​+Wu​
  2. S S S 屬于以 u u u 為根的子樹
  3. S → l c a ( S , T ) S\rightarrow lca(S,T) S→lca(S,T) 路徑對應的 d e p l c a ( S , T ) < d e p u dep_{lca(S,T)}<dep_u deplca(S,T)​<depu​，即路徑還沒有結束。

% 　　是以，我們隻需要統計以 u u u 為根的子樹中，有多少個點的 d e p dep dep 值等于 d e p u + W u dep_u+W_u depu​+Wu​。

　　怎麼求？我們考慮在深度優先搜尋的時候，記錄下 U p [ i ] Up[i] Up[i]，表示已經周遊過的點中，有多少條沒有結束的路徑，滿足路徑開端的 d e p dep dep 值等于 i i i。那麼如果我們要求子樹内有多少個點滿足 d e p dep dep 值等于 i i i，隻需要計算一下周遊子樹前和周遊子樹後 U p [ d e p u + W u ] Up[dep_u+W_u] Up[depu​+Wu​] 的內插補點即可。

　　如此，在遇到一條路徑的開端時，将其按照 d e p dep dep 值加入 U p Up Up 數組中，在遇到路徑結束時，在 U p Up Up 數組中删除這條路徑開端的 d e p dep dep 值（注意不是删除路徑末端的 d e p dep dep 值）。

//求向上的鍊的答案 
int Up[maxn],ans[maxn];
void dfst(int u){
	int c=Up[dep[u]+w[u]];//記錄初始值 
	
	for(int i=head[u];i;i=edges[i].next){
		int v=edges[i].v;
		//Fa[u][k]表示點u的第2^j個父親（倍增求lca用）
		if(v==Fa[u][0]) continue;
		dfst(v);
	}
	
	ans[u]+=Up[dep[u]+w[u]]-c;//增量為子樹中滿足dep值等于dep[u]+w[u]的數量
	
	//更新Up數組
	for(int i=qs[u];i;i=edges[i].next){//将開端和結束資訊拉鍊成一個鄰接表
		//此處edges[i].v==1表示這是一條路徑開端
		//否則說明是一條路徑的末尾
		//edges[i].qidian表示路徑開端的點的編号
		if(edges[i].v==1) Up[dep[u]]++;//加上點u的貢獻 
		else Up[dep[edges[i].qidian]]--;//删除當初的點u的貢獻 
	}
}
向下的鍊

% 　　然後我們來考慮向下的鍊 l c a ( S , T ) → T lca(S,T)\rightarrow T lca(S,T)→T，根據題意，若點 u u u 能觀測到這條路徑當且僅當點 u u u 在 l c a ( S , T ) → T lca(S,T)\rightarrow T lca(S,T)→T 上，且 W u = d i s ( S , T ) − ( d e p T − d e p u ) W_u=dis(S,T)-(dep_T-dep_u) Wu​=dis(S,T)−(depT​−depu​)，化簡得 d e p u − W u = d e p T − d i s ( S , T ) dep_u-W_u=dep_T-dis(S,T) depu​−Wu​=depT​−dis(S,T)

% 　　是以，類似地，對于點 u u u，所有對 a n s u ans_u ansu​ 産生貢獻的鍊 l c a ( S , T ) → T lca(S,T)\rightarrow T lca(S,T)→T 必須同時滿足以下三點。

  1. d e p u − W u = d e p T − d i s ( S , T ) dep_u-W_u=dep_T-dis(S,T) depu​−Wu​=depT​−dis(S,T)
  2. T T T 屬于以 u u u 為根的子樹
  3. d e p l c a ( S , T ) < d e p u dep_{lca(S,T)}<dep_u deplca(S,T)​<depu​，即 l c a ( S , T ) → T lca(S,T)\rightarrow T lca(S,T)→T 已經開始。

% 　　類似地深度優先搜尋的時，記錄下 D n [ i ] Dn[i] Dn[i]，表示已經周遊過的點中，有多少條已經開始的路徑，滿足路徑末端的 d e p dep dep 值減去路徑長度等于 i i i。求子樹資訊仍然計算內插補點即可。

　　 D n Dn Dn 數組的更新也類似。唯一需要注意的是 d e p u − W u dep_u-W_u depu​−Wu​ 的值可能為負，是以需要對數組偏移一下，下面的代碼沒有采用通路時偏移的方法，而是采用了指針整體偏移的方式。

int _dn[maxn<<1];
int *Dn=&_dn[maxn];//指針放在中間位置
void dfed(int u){
	int c=Dn[dep[u]-w[u]];//記錄初始值 
	
	for(int i=head[u];i;i=edges[i].next){
		int v=edges[i].v;
		if(v==Fa[u][0]) continue;
		dfed(v);
	}
	
	ans[u]+=Dn[dep[u]-w[u]]-c;//增量為子樹中滿足要求的總數 
	
	for(int i=qs[u];i;i=edges[i].next){
		if(edges[i].v==1) Dn[dep[u]-edges[i].w]++;//是路徑開端則加上點u的貢獻 
		else  Dn[dep[edges[i].qidian]-edges[i].w]--;//删除當初的點u的貢獻 
	}
}
重複部分

% 　　上面考慮了 S → l c a ( S , T ) S\rightarrow lca(S,T) S→lca(S,T) 和 l c a ( S , T ) → T lca(S,T)\rightarrow T lca(S,T)→T 兩條鍊，是以 l c a ( S , T ) lca(S,T) lca(S,T) 被考慮了兩次，因而需要減去一次。

　　路徑 S i → T j S_i\rightarrow T_j Si​→Tj​ 能對 a n s l c a ( S , T ) ans_{lca(S,T)} anslca(S,T)​ 産生貢獻當且僅當 W l c a ( S , T ) = d e p S − d e p l c a ( S , T ) W_{lca(S,T)}=dep_{S}-dep_{lca(S,T)} Wlca(S,T)​=depS​−deplca(S,T)​　　減去即可。

//LCA[i]=lca(S[i],T[i])
for(int i=1;i<=m;i++) if(dep[S[i]]-w[LCA[i]]==dep[LCA[i]]) --ans[LCA[i]];

完整代碼 

#include<bits/stdc++.h>
using namespace std;
#define maxn 1000010
struct edge{
	int v,next,w,qidian;
	//在圖head意義下，v:端點	w,qidian: 無意義
	
	//在詢問qs意義下，v:鍊的開始為1，鍊的結束為-1
	//w:點對距離 	qidian:詢問的另一個端點 
}edges[maxn<<1];
int n,head[maxn],cnt=0;
//加入圖中的邊 
void ins(int u,int v){
	edges[++cnt]=(edge){v,head[u]};
	head[u]=cnt;
}
//加入點對資訊 
int qs[maxn];
//op:鍊的開始(1)或者結束(-1)
void qns(int u,int op,int w=0,int qidian=0){
	edges[++cnt]=(edge){op,qs[u],w,qidian};
	qs[u]=cnt;
}

//求出深度，父親 
int w[maxn],dep[maxn],Fa[maxn][20];
void predfs(int u,int fa=0){
	dep[u]=dep[fa]+1; Fa[u][0]=fa;
	for(int i=head[u];i;i=edges[i].next){
		int v=edges[i].v;
		if(v==fa) continue;
		predfs(v,u);
	}
}

//倍增求最近公共祖先 
int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=19;i>=0&&dep[x]!=dep[y];i--)
		if(dep[Fa[x][i]]>=dep[y]) x=Fa[x][i];
	if(x==y) return x;
	for(int i=19;i>=0;i--)
		if(Fa[x][i]!=Fa[y][i]){
			x=Fa[x][i];
			y=Fa[y][i];
		}
	return Fa[x][0];
}

//求距離 
int dis(int u,int v){
	int lcas=lca(u,v);
	return dep[u]+dep[v]-dep[lcas]*2;
}

//求向上的鍊的答案 
int Up[maxn],ans[maxn];
void dfst(int u){
	int c=Up[dep[u]+w[u]];//記錄初始值 
	
	for(int i=head[u];i;i=edges[i].next){
		int v=edges[i].v;
		if(v==Fa[u][0]) continue;
		dfst(v);
	}
	
	ans[u]+=Up[dep[u]+w[u]]-c;//增量為子樹中滿足要求的總數
	
	for(int i=qs[u];i;i=edges[i].next){
		if(edges[i].v==1) Up[dep[u]]++;//加上點u的貢獻 
		else Up[dep[edges[i].qidian]]--;//删除當初的點u的貢獻 
	}
}

//求向下的鍊的答案 
int _dn[maxn<<1];
int *Dn;
void dfed(int u){
	int c=Dn[dep[u]-w[u]];//記錄初始值 
	
	for(int i=head[u];i;i=edges[i].next){
		int v=edges[i].v;
		if(v==Fa[u][0]) continue;
		dfed(v);
	}
	
	ans[u]+=Dn[dep[u]-w[u]]-c;//增量為子樹中滿足要求的總數 
	
	for(int i=qs[u];i;i=edges[i].next){
		if(edges[i].v==1) Dn[dep[u]-edges[i].w]++;//加上點u的貢獻 
		else  Dn[dep[edges[i].qidian]-edges[i].w]--;//删除當初的點u的貢獻 
	}
}

int S[maxn],T[maxn],LCA[maxn];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1,a,b;i<n;i++){
		scanf("%d%d",&a,&b);
		ins(a,b);ins(b,a);
	}
	for(int i=1;i<=n;i++)
		scanf("%d",&w[i]);
	
	//預處理資訊 
	predfs(1);
	for(int j=1;j<=19;j++)
		for(int i=1;i<=n;i++)
			Fa[i][j]=Fa[Fa[i][j-1]][j-1];

	//處理向上的鍊 
	for(int i=1;i<=m;i++){
		scanf("%d%d",&S[i],&T[i]);
		LCA[i]=lca(S[i],T[i]);//求lca 
		ans[S[i]]+=(w[S[i]]==0);//當鍊長度為0時特判
		qns(S[i],1);//加傳入連結資訊 
		qns(LCA[i],-1,0,S[i]);//在lca處删除鍊資訊 
	}dfst(1);
	
	//重新處理向下的鍊 
	memset(qs,0,sizeof qs);
	for(int i=1;i<=m;i++){
		int dist=dis(S[i],T[i]);
		ans[T[i]]+=(w[T[i]]==dist);//當鍊長度為0時特判
		qns(T[i],1,dist);//加傳入連結資訊 
		qns(LCA[i],-1,dist,T[i]);//在lca處删除鍊資訊
	}
	
	Dn=&_dn[maxn];//為了适應負數的情況 
	dfed(1);
	
	//去除lca被重複計算的部分 
	for(int i=1;i<=m;i++)
    	if(dep[S[i]]-w[LCA[i]]==dep[LCA[i]])
			--ans[LCA[i]];
	
	for(int i=1;i<=n;i++)
		printf("%d ",ans[i]);
	return 0;
}
最近公共祖先
上一篇: 祖孫詢問-祖孫詢問
下一篇: HDU 2586-How far away（最近公共祖先LCA）

繼續閱讀