jzoj5290 【NOIP2017提高組A組模拟8.17】行程的交集 (樹上路徑交，dfs序+樹狀數組維護姿勢)

#題面

豪哥生活在一個n個點的樹形城市裡面，每一天都要走來走去。雖然走的是比較的多，但是豪哥在這個城市裡面的朋友并不是很多。

當某一天，猴哥給他展現了一下大佬風範之後，豪哥決定要獲得一些交往機會來提升交往能力。豪哥現在已經物色上了一條友，打算和它（豪哥并不讓吃瓜群衆知道性别）交往。豪哥現在spy了一下這個人的所有行程起點和終點，豪哥打算從終點開始走到起點與其相遇。但是豪哥是想找話題的，他想知道以前有多少次行程和此次行程是有交集的，這樣豪哥就可以搭上話了。這個路徑與之前路徑的有交集數量作為豪哥此次的交往機會。

但是豪哥急着要做交往準備，是以算什麼交往機會的小事情就交給你了。

對于另外50%的資料n，m≤200000

#分析

讓我們來看看樹上路徑交可以怎麼表示。畫幾棵樹後可以發現：

令 l c a ( a , b ) = g , l c a ( c , d ) = f 。 若 樹 上 路 徑 [ a , b ] , [ c , d ] 有 交 集 ， 則 g 在 c d 上    或    f 在 a b 上 。 令lca(a,b)=g,lca(c,d)=f。若樹上路徑[a,b],[c,d]有交集，則g在cd上~~或~~f在ab上。 令lca(a,b)=g,lca(c,d)=f。若樹上路徑[a,b],[c,d]有交集，則g在cd上  或  f在ab上。

這個結論并不是那麼好發現（至少我沒發現），可以粗略的感性了解一下：

假設我們現在手上是一條lca深度大的路徑，這條路徑最高可達點就是lca，若lca不在另一條路徑上，又因為他lca深度大，是以不可能在另外一條路徑lca上方，是以就沒有可達點了。

記住這個姿勢，以後會用到。

那麼問題就變成了，在ab上找之前路徑的lca 與 在找覆寫lca的之前路徑。

整體地看，這兩種情況是沒有重合的，因為若ab的lca在cd路徑上，則ab不可能經過cd的lca.

極端情況，容易發現當lca相等的時候需要特判。

##Part1: ab上找之前路徑的lca

靜态樹考慮dfs序。 （動态樹考慮歐拉序）

對于一個點x，a->lca(a,b)這樣的樹鍊如果經過他，則一定是從它的子樹走向它的祖先。

然後就比較顯然了，每多加一個這樣的x，則給他子樹中所有點的權值都+1.

查詢(a,lca(a,b),b)的時候，就用a權+b權-lca權*2.

若a與lca在x的上下兩方，則會被累加到貢獻。

若同時在x的下方，則會被lca權減掉。

##Part2: 覆寫lca的之前路徑

同樣地考慮dfs序，

很友善的樹上字首和。若有一條路徑(a,b)，則給lca(a,b) +1，a-1,b-1.然後查詢一個點到根的權值和，這是離線時的套路。

但這題這樣不好做，因為不能每一次都重構樹，于是我們變一下，變成類似樹上字尾和的東西。

對于一條路徑(a,b)，給a+1,b+1,lca-2.

一個點的子樹權值和就是他的權值。

用兩樹狀數組維護一下dfs序上的資訊，我們就把這道題給搞定了。

這題的坑點主要在于，兩個樹狀數組維護的資訊意義是不一樣的，壓根不可以相提并論。

#Demo

#include <cstdio>
#include <iostream>
#define lowbit(x) ((x)&-(x))
#define treeSum(t,x) (sum(t,R[x])-sum(t,L[x]-1))
using namespace std;
const int N=2e5+10;
int n,m,L[N],R[N],stm;
int tot,to[N*2],next[N*2],final[N],app[N];
int f[N][19],dep[N];
int t1[N],t2[N],ans;
void change(int *tr,int x,int v) {for (; x<=n; x+=lowbit(x)) tr[x]+=v;}
int sum(int *tr,int x) {int ret=0; for (; x; x-=lowbit(x)) ret+=tr[x]; return ret;}

void link(int x,int y) {
	to[++tot]=y,next[tot]=final[x],final[x]=tot;
}
void dfs(int x,int fa) {
	L[x]=++stm;
	f[x][0]=fa; for (int i=1; i<19; i++) f[x][i]=f[f[x][i-1]][i-1];
	dep[x]=dep[fa]+1;
	for (int i=final[x]; i; i=next[i]) if (to[i]!=fa) dfs(to[i],x);
	R[x]=stm;
}
int lca(int x,int y) {
	if (dep[x]<dep[y]) swap(x,y);
	for (int i=18; i>=0; i--) if (dep[f[x][i]]>=dep[y]) x=f[x][i];
	if (x==y) return x;
	for (int i=18; i>=0; i--) if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; 
	return f[x][0];
}
void calcAns(int x,int y,int lca) {
	ans+=treeSum(t1,lca);
	ans+=sum(t2,L[x])+sum(t2,L[y])-sum(t2,L[lca])*2;
}
int main() {
	freopen("3.in","r",stdin);
	cin>>n;
	for (int i=1; i<n; i++) {
		int u,v; scanf("%d %d\n",&u,&v); link(u,v),link(v,u);
	}
	dfs(1,0);
	cin>>m;
	for (int i=1; i<=m; i++) {
		int u,v; scanf("%d %d\n",&u,&v);
		int g=lca(u,v);
		ans=0;
		calcAns(u,v,g);
		printf("%d\n",ans+app[g]);
		app[g]++;
		change(t1,L[u],1);
		change(t1,L[v],1);
		change(t1,L[g],-2);
		
		change(t2,L[g],1);
		change(t2,R[g]+1,-1);
	}
}