时间复杂度证明题，zhoukangyang指导了我好久才明白。。。
Trie树启发式合并，代码异常简洁，时间复杂度还是 (O(nlog n)) 的。
反正代码也不长，就550B，直接放代码，等你看懂了我在干什么再来证复杂度吧。
const int N=600005;
int ch[N][26],n,cnt[N],tot,ans,id;
int merge(int x,int y){
if(!x||!y)return x|y;
int u=++tot;
rep(i,0,25)ch[u][i]=merge(ch[x][i],ch[y][i]);
return u;
}
void dfs(int u,int dep){
if(!u)return;
tot=n;int x=++tot;
rep(i,0,25)x=merge(x,ch[u][i]);
cnt[dep]+=tot-n-1;
rep(i,0,25)dfs(ch[u][i],dep+1);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
rep(i,2,n){
char c;int x,y;
cin>>x>>y>>c,ch[x][c-'a']=y;
}
dfs(1,1),ans=N;
rep(i,1,n)if(ckmin(ans,n-cnt[i]))id=i;
cout<<ans<<'
'<<id<<'
';
}
嗯对，就这玩意，感觉很假，但是确实是 (O(nlog n)) 的。
关键在于那个 merge 。手玩一下就很清楚了，每次 dfs 的时候把 (x) 的子树全部 merge ，总新建节点次数不会超过 (x) 的轻子树大小之和！
轻子树和是 (O(nlog n)) 的，因为每一个节点只有在往根跳到轻链才会被统计到一次，而根据重链剖分性质这个次数是 (O(log n)) 的 。
所以复杂度就是 (O(nlog n)) 了。