搬家一个月，庆祝一下

啪啪啪啪啪啪啪啪啪啪❀❀❀❀

题目传送门

分析：

这什么奇奇怪怪的OJ，以前从来不知道的2333

以前只知道合并两个连通块时，其中一边直径端点为A,B，另一边为C,D

D=max( dis(A,B) , dis(A,C) , dis(A,D) , dis(B,C) , dis(B,D) , dis(C,D) )

原来合并两颗就在原树上可能交叉的虚树，竟然也可以用这个

而且多条直径也不会影响答案？？

细想一下貌似很有道理的亚子。。。

记录记录2333

调了半天

这个歪歪扣不仅丧病而且脑子不太好使，虚树上两点之间连边距离不是1

太菜了dbq

#include
#include
#include
#include
#include
#include
#include

#define maxn 500005
#define INF 0x3f3f3f3f

using namespace std;

inline long long getint()
{
long long num=,flag=;char c;
while((c=getchar())<''||c>'')if(c=='-')flag=-;
while(c>=''&&c<='')num=num*+c-,c=getchar();
return num*flag;
}

int n,m,N;
int fir[maxn],nxt[maxn],to[maxn],cnt;
int fa[maxn],dpt[maxn],tp[maxn],sz[maxn],son[maxn];
int In[maxn],Out[maxn],cur;
int stk[maxn],top;
int Id[maxn];
int h[maxn],f[maxn];
vectorH[maxn];
int Rt[maxn][];
mapM;
vectorG[maxn];
inline bool cmp(int x,int y){return In[x]<In[y];}

inline void newnode(int u,int v)
{to[++cnt]=v,nxt[cnt]=fir[u],fir[u]=cnt;}

inline void dfs1(int u)
{
sz[u]=;
for(int i=fir[u];i;i=nxt[i])
if(to[i]!=fa[u])
{
dpt[to[i]]=dpt[u]+,fa[to[i]]=u;
dfs1(to[i]);
sz[u]+=sz[to[i]];if(sz[to[i]]>sz[son[u]])son[u]=to[i];
}
}

inline void dfs2(int u,int ac)
{
In[u]=++cur,tp[u]=ac;
if(son[u])dfs2(son[u],ac);
for(int i=fir[u];i;i=nxt[i])if(to[i]!=fa[u]&&to[i]!=son[u])dfs2(to[i],to[i]);
Out[u]=cur;
}

inline int LCA(int u,int v)
{
while(tp[u]!=tp[v])
{
if(dpt[tp[u]]<dpt[tp[v]])swap(u,v);
u=fa[tp[u]];
}
return dpt[u]<dpt[v]?u:v;
}

inline void getdp(int u,int lst)
{
for(int i=G[u].size()-;~i;i--)if(G[u][i]!=lst)
f[G[u][i]]=f[u]+abs(dpt[u]-dpt[G[u][i]]),getdp(G[u][i],u);
}

inline void solve(int x)
{
int K=H[x].size();top=;
for(int i=;if[rt])rt=h[i];
Rt[x][]=rt;
f[rt]=;getdp(rt,rt);
for(int i=;i<=K;i++)if(f[h[i]]>f[rt])rt=h[i];
Rt[x][]=rt;
for(int i=;i<=K;i++)G[h[i]].clear();
}

inline int getdis(int u,int v)
{return dpt[u]+dpt[v]-*dpt[LCA(u,v)];}

inline int getans(int x,int y)
{
int A=Rt[x][],B=Rt[x][],C=Rt[y][],D=Rt[y][];
return max(max(getdis(A,C),getdis(A,D)),max(getdis(B,C),getdis(B,D)));
}

int main()
{
while(~scanf("%d%d",&n,&m))
{
M.clear();
memset(fir,,sizeof fir),cnt=;
memset(son,,sizeof son);cur=;
memset(fa,,sizeof fa),memset(sz,,sizeof sz);
memset(tp,,sizeof tp),memset(dpt,,sizeof dpt);
memset(Rt,,sizeof Rt);memset(Id,,sizeof Id);
memset(In,,sizeof In),memset(Out,,sizeof Out);
for(int i=;i<=n;i++) { string tmp;cin>>tmp;
if(!M.count(tmp))M[tmp]=++N;
Id[i]=M[tmp];
H[M[tmp]].push_back(i);
}
for(int i=;i>tmp1>>tmp2;
if(!M.count(tmp1)||!M.count(tmp2))printf("-1\n");
else printf("%d\n",getans(M[tmp1],M[tmp2])+);
}
for(int i=;i<=N;i++)H[i].clear();N=;
}
}