Description

Input

Output

Sample Input

3 3 1
1 2
2 3
1 2 3
1 1 3
3 1 3

Sample Output

1
1
3

Data Constraint

Hint

樣例2、3、4見所附文件

Solution

• 題目給出一個無根樹，于是我們先以 1 位根，將樹轉成有根樹，可以發現這不影響答案。

• 同時記錄點的深度和父親等信息，用倍增預處理出點的 Lca 信息。

• 接著，對于一個詢問，求出兩兩之間的 Lca ，分類討論其擺布情況，通過深度算出答案即可。

• 特別注意的是分類討論情況繁瑣，切勿漏判，時間復雜度為 O((N+Q)?log?N) 。

Code

#include<cstdio> #include<algorithm> #include<cmath> using namespace std; const int N=2e5+1; int tot; int first[N],next[N<<1],en[N<<1]; int dep[N],f[N][18]; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } inline int max(int x,int y) {return x>y?x:y; } inline void insert(int x,int y) {next[++tot]=first[x];first[x]=tot;en[tot]=y; } inline void dfs(int x) {dep[x]=dep[f[x][0]]+1;for(int i=first[x];i;i=next[i])if(en[i]!=f[x][0]){f[en[i]][0]=x;dfs(en[i]);} } inline int lca(int x,int y) {if(dep[y]>dep[x]) swap(x,y);for(int i=log2(dep[x]);i>=0;i--)if(dep[f[x][i]]>=dep[y]) x=f[x][i];if(x==y) return x;for(int i=log2(dep[x]);i>=0;i--)if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];return f[x][0]; } int main() {int n=read(),q=read(),num=read();for(int i=1;i<n;i++){int x=read(),y=read();insert(x,y);insert(y,x);}dfs(1);for(int j=1;j<=17;j++)for(int i=1;i<=n;i++)f[i][j]=f[f[i][j-1]][j-1];while(q--){int a=read(),b=read(),c=read(),ans=0;int ab=lca(a,b),ac=lca(a,c),bc=lca(b,c);if(ab==b){if(dep[ac]<=dep[b]) ans=1; else ans=dep[ac]-dep[b]+1;}elseif(ab==a){if(dep[bc]<=dep[a]) ans=dep[b]-dep[a]+1; else ans=dep[b]-dep[bc]+1;}else{if(ac==a) ans=dep[a]+dep[b]-2*dep[ab]+1; elseif(bc==b) ans=1; elseif(bc==c) ans=dep[b]-max(dep[c],dep[ab])+1; elseif(ac==c){ans=dep[b]-dep[ab]+1;if(dep[c]>dep[ab]) ans+=dep[c]-dep[ab];}elseif(bc==ab && ab==ac) ans=dep[b]-dep[bc]+1; elseif(dep[bc]>dep[ab]) ans=dep[b]-dep[bc]+1; elseif(dep[ac]<dep[ab]){if(dep[ab]>dep[bc]) ans=dep[b]-dep[ab]+1; elseans=dep[ab]+dep[c]-2*dep[ac]+1;}elseif(dep[ac]>=dep[ab]) ans=dep[ac]+dep[b]-2*dep[ab]+1;}printf("%d\n",ans);}return 0; } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的JZOJ 5257. 小X的佛光的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。