【USACO10HOL】 Cow Politics

迈不过友情╰ 2021-10-19 11:10 254阅读 0赞

# 题目大意 #

给出k组点，求出组内两点间的最大距离

# 核心思路 #

考虑贪心，每组内的最深一点一定是两最远距离点对之一。

证明很简单，可以分为在该点的祖先相同和祖先不同的情况。如果点对其中一个为另一个的祖先的话，一定会选择改组内最深的点，如果祖先不同，因为他们到lca的距离可以被等价地看为在该点的祖先上，所以也可以应用上述的结论。综上每组内的最深一点一定是两最远距离点对之一。

接下来的任务就是暴力地求解其余点到该最深点的距离。

代码如下：

#include<bits/stdc++.h> using namespace std; #define REP(i,e,s) for(register int i=e; i<=s; i++) #define DREP(i,e,s) for(register int i=e; i>=s; i--) int read() { int x=0,f=1,ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int MAXN=200000+10; int n,m,a[MAXN],head[MAXN],_next[MAXN],to[MAXN],cnt,fa[MAXN][20],dept[MAXN],ans[MAXN],apd[MAXN],apdi[MAXN]; void addedge(int u,int v) { cnt++; _next[cnt]=head[u]; head[u]=cnt; to[cnt]=v; } void dfs(int x) { if(apd[a[x]]<=dept[x]) { apd[a[x]]=dept[x]; apdi[a[x]]=x; } for(int i=head[x]; i; i=_next[i]) { int y=to[i]; //if(fa[x][0]==y) continue; fa[y][0]=x; dept[y]=dept[x]+1; dfs(y); } } int lca(int u,int v) { if(dept[u]<dept[v]) swap(u,v); int h1=dept[u]-dept[v]; DREP(i,17,0) if((1<<i)&h1) u=fa[u][i]; if(u==v) return u; DREP(i,18,0) if(fa[u][i]!=fa[v][i]) { u=fa[u][i]; v=fa[v][i]; } return fa[u][0]; } int main() { int n=read(),k=read(); int _root; REP(i,1,n) { a[i]=read(); int v=read(); addedge(v,i); if(v==0) _root=i; } dept[_root]=1; dfs(_root); REP(j,1,17) REP(i,1,n) fa[i][j]=fa[fa[i][j-1]][j-1]; //printf("%d %d\n",fa[2][0],fa[5][0]); REP(i,1,n) { //printf("%d %d %d\n",i,apdi[a[i]],lca(i,apdi[a[i]])); ans[a[i]]=max(ans[a[i]],apd[a[i]]+dept[i]-2*dept[lca(apdi[a[i]],i)]); } REP(i,1,k) printf("%d\n",ans[i]); return 0; }

转载于:https://www.cnblogs.com/MicDZ/p/USACO10HOL-CowPolitics.html