J-Tree

Cosmic_Tree題解

賽時(shí)隊(duì)友想到了預(yù)處理$s\to t$路徑上的點(diǎn)最遠(yuǎn)到達(dá)的點(diǎn)，后面貪心做的一直wa。正解是dp。

---

下面的$\text{solve}(l,r,\text{op})$函數(shù)中，當(dāng)$l=r$時(shí)不滿足題意不合法，當(dāng)$\text{op}=0$表示當(dāng)前是第一個(gè)人操作，也就是第二個(gè)人走到了不合法的$l=r$的局面，而第二個(gè)人想要結(jié)果盡可能小，因此需要返回$\text{Inf}$，類似的$\text{op}=1$時(shí)返回$?\text{Inf}$

#include<bits/stdc++.h> using namespace std; using ll=long long; template <class T=int> T rd() {T res=0;T fg=1;char ch=getchar();while(!isdigit(ch)) {if(ch=='-') fg=-1;ch=getchar();}while( isdigit(ch)) res=(res<<1)+(res<<3)+(ch^48),ch=getchar();return res*fg; } const int N=500010; int h[N],e[2*N],ne[2*N],idx; void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;} int n,s,t; int d[N],to[N]; int f[N],cnt; int dfs(int u,int fa) {int fl=0;if(u==t) fl=1;for(int i=h[u];i!=-1;i=ne[i]){int v=e[i];if(v==fa) continue;int tmp=dfs(v,u);fl|=tmp;if(tmp) to[u]=v;elsed[u]=max(d[u],d[v]+1);}return fl; } int L[N][21],R[N][21]; int lg[N]; void init() {lg[0]=1;for(int i=2;i<=cnt;i++) lg[i]=lg[i>>1]+1;for(int i=1;i<=cnt;i++) L[i][0]=f[i]+i-1;for(int i=1;i<=cnt;i++) R[i][0]=f[i]+cnt-i;for(int j=1;j<=lg[cnt];j++)for(int i=1;i+(1<<j)-1<=cnt;i++){L[i][j]=max(L[i][j-1],L[i+(1<<j-1)][j-1]);R[i][j]=max(R[i][j-1],R[i+(1<<j-1)][j-1]);} } int ql(int l,int r){int len=lg[r-l+1];return max(L[l][len],L[r-(1<<len)+1][len]);} int qr(int l,int r){int len=lg[r-l+1];return max(R[l][len],R[r-(1<<len)+1][len]);} int solve(int l,int r,int op) {if(l==r){if(op==0) return 0x3f3f3f3f;elsereturn -0x3f3f3f3f;}if(op==0) return max((f[l]+l-1)-qr(l+1,r),solve(l+1,r,1));elsereturn min(ql(l,r-1)-(f[r]+cnt-r),solve(l,r-1,0)); } int main() {memset(h,-1,sizeof h);n=rd(),s=rd(),t=rd();for(int i=1;i<n;i++){int u=rd(),v=rd();add(u,v),add(v,u);}dfs(s,0);f[++cnt]=d[s];int tmp=s;while(tmp!=t) {tmp=to[tmp];f[++cnt]=d[tmp];}init();printf("%d\n",solve(1,cnt,0));return 0; }

總結(jié)

以上是生活随笔為你收集整理的2021牛客暑期多校训练营8 J-Tree（思维dp+rmq）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。