搬家一个月，庆祝一下
啪啪啪啪啪啪啪啪啪啪❀❀❀❀
题目传送门
分析：
这什么奇奇怪怪的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<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<iostream> #include<map> #include<string> #define maxn 500005 #define INF 0x3f3f3f3f using namespace std; inline long long getint() { long long num=0,flag=1;char c; while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1; while(c>='0'&&c<='9')num=num*10+c-48,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]; vector<int>H[maxn]; int Rt[maxn][2]; map<string,int>M; vector<int>G[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]=1; for(int i=fir[u];i;i=nxt[i]) if(to[i]!=fa[u]) { dpt[to[i]]=dpt[u]+1,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()-1;~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=0; for(int i=0;i<K;i++)h[i+1]=H[x][i]; sort(h+1,h+K+1,cmp); for(int i=K-1;i;i--)h[++K]=LCA(h[i],h[i+1]); sort(h+1,h+K+1,cmp);K=unique(h+1,h+K+1)-h-1; stk[++top]=h[1]; for(int i=2;i<=K;i++) { while(top&&Out[stk[top]]<In[h[i]])top--; if(top)G[stk[top]].push_back(h[i]),G[h[i]].push_back(stk[top]); stk[++top]=h[i]; } int rt=h[1]; f[rt]=0;getdp(rt,rt); for(int i=1;i<=K;i++)if(f[h[i]]>f[rt])rt=h[i]; Rt[x][0]=rt; f[rt]=0;getdp(rt,rt); for(int i=1;i<=K;i++)if(f[h[i]]>f[rt])rt=h[i]; Rt[x][1]=rt; for(int i=1;i<=K;i++)G[h[i]].clear(); } inline int getdis(int u,int v) {return dpt[u]+dpt[v]-2*dpt[LCA(u,v)];} inline int getans(int x,int y) { int A=Rt[x][0],B=Rt[x][1],C=Rt[y][0],D=Rt[y][1]; 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,0,sizeof fir),cnt=0; memset(son,0,sizeof son);cur=0; memset(fa,0,sizeof fa),memset(sz,0,sizeof sz); memset(tp,0,sizeof tp),memset(dpt,0,sizeof dpt); memset(Rt,0,sizeof Rt);memset(Id,0,sizeof Id); memset(In,0,sizeof In),memset(Out,0,sizeof Out); for(int i=1;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=1;i<n;i++) { int u=getint(),v=getint(); newnode(u,v),newnode(v,u); } dfs1(1),dfs2(1,1); for(int i=1;i<=N;i++)solve(i); while(m--) { string tmp1,tmp2; cin>>tmp1>>tmp2; if(!M.count(tmp1)||!M.count(tmp2))printf("-1 "); else printf("%d ",getans(M[tmp1],M[tmp2])+1); } for(int i=1;i<=N;i++)H[i].clear();N=0; } }
