牛客巅峰赛第7场代码
#include<bits/stdc++.h>
#define fgx cerr<<"-----------------------"<<endl
using namespace std;
#define LL long long
#define DB double
#define pb push_back
#define pii pair<int,int>
#define mpt make_pair
#define fr first
#define sc second
#define M 100020//Size
#define INF 1000000000
#define INFLL 1000000000000000000
inline int read(){
int nm=0,fh=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') fh=-1;
for(;isdigit(c);c=getchar()) nm=nm*10+c-'0';
return nm*fh;
}
#define mod 1000000007//About
inline int add(int x,int y){return (x+y>=mod)?(x+y-mod):(x+y);}
inline int mns(int x,int y){return (x-y<0)?(x-y+mod):(x-y);}
inline int mul(LL x,LL y){return x*y%mod;}
inline void upd(int &x,int y){x=(x+y>=mod)?(x+y-mod):(x+y);}
inline void dec(int &x,int y){x=(x-y<0)?(x-y+mod):(x-y);}
inline int qpow(int x,LL sq){int res=1;for(;sq;sq>>=1,x=mul(x,x))if(sq&1)res=mul(res,x);return res;}
const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param n int整型 节点个数
* @param u int整型vector
* @param v int整型vector
* @return int整型
*/
int to[M<<1],nt[M<<1],fs[M],tot;
int F[M],G[M],H[M],n,mx;
inline void link(int x,int y){to[++tot]=y,nt[tot]=fs[x],fs[x]=tot;}
inline void dfs(int x,int last=0){
for(int i=fs[x],y;i;i=nt[i]) if((y=to[i])^last)
dfs(y,x),mx=max(mx,F[y]+1+F[x]),F[x]=max(F[x],F[y]+1);
}
inline void dfs2(int x,int now,int last=0){
G[x]=now; int Mx=-(n<<1),Mx2=-(n<<1);
for(int i=fs[x],y;i;i=nt[i]) if((y=to[i])^last){
int tmp=F[y]+1;
if(tmp>Mx) Mx2=Mx,Mx=tmp;
else if(tmp>Mx2) Mx2=tmp;
}
H[x]=Mx2;
for(int i=fs[x],y;i;i=nt[i]) if((y=to[i])^last){
int tmp=(F[y]+1==Mx)?Mx2:Mx;
dfs2(y,max(now,tmp)+1,x);
}
}
int PointsOnDiameter(int N, vector<int>& u, vector<int>& v) {
// write code here
n=N; //fgx;
mx=0;
for(int i=0;i<n-1;i++) link(u[i],v[i]),link(v[i],u[i]);
dfs(1); dfs2(1,0);
int ans=0;
//for(int i=1;i<=n;i++)
// printf("%d %d %d\n",F[i],G[i],H[i]);
for(int i=1;i<=n;i++){
int tmp=F[i]+max(G[i],H[i]);
if(tmp==mx) ans++;
} return ans;
}
}t;
#题解#
