題目鏈接

https://atcoder.jp/contests/agc005/tasks/agc005_e

題解

完了真的啥都不會了……

首先，顯然如果某條A樹的邊對應B樹上的距離大于等于\(3\), 且A能走到該邊的某個端點，那么答案就是\(-1\).
A能走到某個點當且僅當從A的起點到這個點的路徑上每個點與A起點的距離都小于與B起點的距離。
然后直接在A樹上從根開始DFS，如果走不到了就返回，否則用與\(y\)的距離更新答案；同時在遍歷每條邊的時候判斷是否可以\(-1\).
時間復雜度\(O(n\log n)\), 但是由于距離不超過\(3\)的特殊性可以優化成\(O(n)\).

上面的性質我都發現了，可是我做不出來這題……到底是什么情況……

代碼

#include<cstdio> #include<cstdlib> #include<iostream> #include<cassert> using namespace std;const int N = 2e5; const int lgN = 18; const int INF = 1e7; struct Edge {int v,nxt; } e1[(N<<1)+3],e2[(N<<1)+3]; int fe1[N+3],fe2[N+3]; int dep1[N+3],dep2[N+3]; int fa2[N+3][lgN+3]; int n,en1,en2,s1,s2,ans;void addedge1(int u,int v) {en1++; e1[en1].v = v;e1[en1].nxt = fe1[u]; fe1[u] = en1; } void addedge2(int u,int v) {en2++; e2[en2].v = v;e2[en2].nxt = fe2[u]; fe2[u] = en2; }void dfs1(int u,int prv) {for(int i=fe1[u]; i; i=e1[i].nxt){int v = e1[i].v;if(v==prv) continue;dep1[v] = dep1[u]+1;dfs1(v,u);} }void dfs2(int u) {for(int i=1; i<=lgN; i++) fa2[u][i] = fa2[fa2[u][i-1]][i-1];for(int i=fe2[u]; i; i=e2[i].nxt){int v = e2[i].v;if(v==fa2[u][0]) continue;fa2[v][0] = u; dep2[v] = dep2[u]+1;dfs2(v);} }int LCA(int u,int v) {if(dep2[u]<dep2[v]) swap(u,v);int dif = dep2[u]-dep2[v];for(int i=0; i<=lgN; i++){if(dif&(1<<i)) {u = fa2[u][i];}}if(u==v) return u;for(int i=lgN; i>=0; i--){if(fa2[u][i]!=fa2[v][i]) {u = fa2[u][i],v = fa2[v][i];}}return fa2[u][0]; }void dfs(int u,int fa) {if(dep1[u]>=dep2[u]) {return;}ans = max(ans,dep2[u]);for(int i=fe1[u]; i; i=e1[i].nxt){int v = e1[i].v;if(v==fa) continue;if(dep2[u]+dep2[v]-2*dep2[LCA(u,v)]>2) {ans = INF; return;}dfs(v,u);} }int main() {scanf("%d%d%d",&n,&s1,&s2);for(int i=1; i<n; i++){int u,v; scanf("%d%d",&u,&v);addedge1(u,v); addedge1(v,u);}for(int i=1; i<n; i++){int u,v; scanf("%d%d",&u,&v);addedge2(u,v); addedge2(v,u);}dfs1(s1,0); dfs2(s2);ans = 0; dfs(s1,0);printf("%d\n",ans==INF?-1:ans*2);return 0; }

總結

以上是生活随笔為你收集整理的AtCoder AGC005E Sugigma: The Showdown (博弈论)的全部內容，希望文章能夠幫你解決所遇到的問題。

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