思路：

　　虚树+乱搞；

 

代码：

#include 
     
      using namespace std;#define maxn 300005#define INF 0x3f3f3f3fstruct KiType {    int id,key;    bool operator<(const KiType pos)const    {        return key
      

que;inline void in(int &now){ char Cget=getchar();now=0; while(Cget>'9'||Cget<'0')Cget=getchar(); while(Cget>='0'&&Cget<='9') { now=now*10+Cget-'0'; Cget=getchar(); }}inline void edge_add(int u,int v){ E[++cnt]=head[u],V[cnt]=v,head[u]=cnt; E[++cnt]=head[v],V[cnt]=u,head[v]=cnt;}inline void edge_add1(int u,int v){ if(deep[u]

size[lar[now]]) lar[now]=V[i]; }}void dfs2(int now,int chain){ top[now]=chain,id[now]=++cnt,id_[cnt]=now; if(lar[now]) dfs2(lar[now],chain); for(int i=head[now];i;i=E[i]) { if(V[i]==lar[now]||V[i]==f[now]) continue; dfs2(V[i],V[i]); } ri[now]=cnt;}inline int find(int x,int y){ while(top[x]!=top[y]) { if(deep[top[x]]

>1; pos_=up(now,pos_-dis[fa]+deep[fa]+1); pos_=size[pos_]-size[now]; sum[bel[now]]+=pos_,sum[bel[fa]]-=pos_; }cur: sum[bel[now]]+=size[now]; for(int i=head[now];i;i=E[i]) { if(V[i]==fa) continue; sum[bel[now]]-=size[V[i]]; Count(V[i],now); }}void clear(int now,int fa){ for(int i=head[now];i;i=E[i]) { if(fa==V[i]) continue; clear(V[i],now); } head[now]=0,sum[now]=0,dis[now]=0,vis[now]=false; bel[now]=0,dis[now]=INF;}int main(){ freopen("worldtree.in","r",stdin); freopen("worldtree.out","w",stdout); in(n);int u,v; for(int i=1;i

ri[sta[v]]) { if(pos) edge_add1(pos,sta[v]); pos=sta[v],v--; } if(pos) { int lca=find(pos,now); if(lca!=pos) edge_add1(pos,lca); if(lca!=sta[v]) sta[++v]=lca; } sta[++v]=now; } while(v>1) edge_add1(sta[v],sta[v-1]),v--; while(!que.empty()) { int now=que.front();que.pop(),if_[now]=false; for(int i=head[now];i;i=E[i]) { if(dis[V[i]]>dis[now]+W[i]) { dis[V[i]]=dis[now]+W[i]; bel[V[i]]=bel[now]; if(!if_[V[i]]) if_[V[i]]=true,que.push(V[i]); } else if(dis[V[i]]==dis[now]+W[i]) { if(bel[now]