政党1最大的两只奶牛的距离是3（也就是奶牛3和奶牛6的距离）。政党2最大的两只奶牛的距离是2（也就是奶牛2和4，4和5，还有5和2之间的距离）。 帮助奶牛们求出每个政党的范围。
政党1最大的两只奶牛的距离是3（也就是奶牛3和奶牛6的距离）。政党2最大的两只奶牛的距离是2（也就是奶牛2和4，4和5，还有5和2之间的距离）。 帮助奶牛们求出每个政党的范围。其实就是树的距离。就是那个两遍$bfs$的东西
对每个政党都做一遍树的距离就好了
找一个深度最大的点，然后与同政党的所有点分别求一下$lca$，取个$max$
这样复杂度是$O(nlogn)$的（每个节点只会访问一次，$lca$效率$O(logn)$）
至于$lca$求法就随意了，这里写的是树剖
#include <bits/stdc++.h> using namespace std ; #define N 400010 int n , k , head[ N ] , cnt , s ; int a[ N ] , fa[ N ] ; int dep[ N ] , siz[ N ] , top[ N ] ; int mx[ N ] ; struct node { int to , nxt ; } e[ N ] ; vector < int > vt[ N ] ; void ins( int u , int v ) { e[ ++ cnt ].to = v ; e[ cnt ].nxt = head[ u ] ; head[ u ] = cnt ; } void dfs1( int u ) { siz[ u ] = 1 ; for( int i = head[ u ] ; i ; i = e[ i ].nxt ) { if( e[ i ].to == fa[ u ] ) continue ; dep[ e[ i ].to ] = dep[ u ] + 1 ; dfs1( e[ i ].to ) ; siz[ u ] += siz[ e[ i ].to ] ; } } void dfs2( int u , int topf ) { top[ u ] = topf ; int k = 0 ; for( int i = head[ u ] ; i ; i = e[ i ].nxt ) { if( e[ i ].to == fa[ u ] ) continue ; if( siz[ e[ i ].to ] > siz[ k ] ) k = e[ i ].to ; } if( !k ) return ; dfs2( k , topf ) ; for( int i = head[ u ] ; i ; i = e[ i ].nxt ) { if( e[ i ].to == k || e[ i ].to == fa[ u ] ) continue ; dfs2( e[ i ].to , e[ i ].to ) ; } } int lca( int x , int y ) { while( top[ x ] != top[ y ] ) { if( dep[ top[ x ] ] < dep[ top[ y ] ] ) swap( x , y ) ; x = fa[ top[ x ] ] ; } if( dep[ x ] > dep[ y ] ) swap( x , y ) ; return x ; } bool cmp( int a , int b ) { return dep[ a ] > dep[ b ] ; } int main() { scanf( "%d%d" , &n , &k ) ; for( int i = 1 ; i <= n ; i ++ ) { int p ; scanf( "%d%d" , &a[ i ] , &p ) ; fa[ i ] = p ; if( p ) ins( i , p ) , ins( p , i ) ; vt[ a[ i ] ].push_back( i ) ; if( p == 0 ) s = i ; } dfs1( s ) ; dfs2( s , s ) ; for( int i = 1 ; i <= k ; i ++ ) { int ans = 0 ; sort( vt[ i ].begin() , vt[ i ].end() , cmp ) ; for( int j = 1 , len = vt[ i ].size() ; j < len ; j ++ ) { int l = lca( vt[ i ][ 0 ] , vt[ i ][ j ] ) ; ans = max( ans , dep[ vt[ i ][ 0 ] ] + dep[ vt[ i ][ j ] ] - 2 * dep[ l ] ) ; } printf( "%d\n" , ans ) ; } return 0 ; }
[BZOJ1776][Usaco2010 Hol]cowpol 奶牛政坛
原文：https://www.cnblogs.com/henry-1202/p/BZOJ1776.html