【题目分析】

    这题好基啊。

    先把分治树搞出来。然后每个节点两个堆。

    第一个堆保存这个块里的所有点（即分治树中的所有儿子）到分治树上的父亲的距离。

    第二个堆保存分治树子树中所有儿子第一个堆的最大值。

    建一个答案堆，表示所有节点第二个堆的最大值和次大值的和。

    然后就是维护。

    两点间距离用LCA转RMQ

    调了4h，代码一度改到7k

【代码】

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;#define maxe 200005#define maxn 100005#define inf (0x3f3f3f3f)#define F(i,j,k) for (int i=j;i<=k;++i)#define D(i,j,k) for (int i=j;i>=k;--i) int h[maxe],to[maxe],ne[maxe],en=0,ban[maxn],n,m,rt,now,dst[maxn],Tree_rt,col[maxn],ans=-1,x,aim;int b[maxn<<2],cnt=0,tag=0,pos[maxn],c[maxn<<2][20],_log[maxn<<2]; void add(int a,int b) {to[en]=b;ne[en]=h[a];h[a]=en++;}struct Heap{    priority_queue 
          
            heap,del; void Ins(int x){heap.push(x);} void Del(int x){del.push(x);} void Pop(){while (del.size()&&del.top()==heap.top()) del.pop(),heap.pop(); heap.pop();} int Top(){while (del.size()&&del.top()==heap.top()) del.pop(),heap.pop(); return heap.top();} int S_Top(){int tmp=Top(),ret;Pop();ret=Top();Ins(tmp);return ret; } int Size(){return heap.size()-del.size();}}s1[maxn],s2[maxn],lst; int mx[maxn],siz[maxn],size,fa[maxn];char opt[11]; void dfs(int o,int fa){ if (!tag)b[++cnt]=o,pos[o]=cnt; siz[o]=1;mx[o]=0; for (int i=h[o];i>=0;i=ne[i]) if (!ban[to[i]]&&to[i]!=fa) { dfs(to[i],o); if (!tag) b[++cnt]=o; siz[o]+=siz[to[i]]; if (siz[to[i]]>mx[o]) mx[o]=siz[to[i]]; }} void dfs_rt(int o,int fa){ if (max(mx[o],size-siz[o])
           
            =0;i=ne[i]) if (!ban[to[i]]&&to[i]!=fa) dfs_rt(to[i],o);} int lca(int a,int b){ int pa=pos[a],pb=pos[b]; if (pa>pb) swap(pa,pb); int l=_log[pb-pa+1]; return min(c[pa][l],c[pb-(1<
            
             =0;i=ne[i]) if (!ban[to[i]]&&to[i]!=fa) dfs_add(to[i],o);} void Divide(int o,int fat){ int root; dfs(o,-1); size=siz[o]; now=inf; dfs_rt(o,-1); root=rt; if (fat) fa[root]=fat; ban[root]=1; aim=fat; dfs_add(root,-1); s2[fat].Ins(s1[root].Top()); if (!col[root]) s2[root].Ins(0); for (int i=h[root];i>=0;i=ne[i]) if (!ban[to[i]]) Divide(to[i],root); if (s2[root].Size()>=2) { ans=max(ans,s2[root].Top()+s2[root].S_Top()); lst.Ins(s2[root].Top()+s2[root].S_Top()); }} void dfs_dist(int o,int fat){ for (int i=h[o];i>=0;i=ne[i]) if (to[i]!=fat) dst[to[i]]=dst[o]+1,dfs_dist(to[i],o);} void Delete(int o){ if (s2[o].Size()>=2) lst.Del(s2[o].Top()+s2[o].S_Top()); s2[o].Del(0); if (s2[o].Size()>=2) { ans=max(ans,s2[o].Top()+s2[o].S_Top()); lst.Ins(s2[o].Top()+s2[o].S_Top()); } if (s2[o].Size()>0) ans=max(ans,0); int now=o; while (now) { int fat=fa[now]; if (s2[fat].Size()>=2) lst.Del(s2[fat].Top()+s2[fat].S_Top()); int tmp=s1[now].Top(); s1[now].Del(dist(o,fat)); if (s1[now].Size()==0||tmp!=s1[now].Top()) { s2[fat].Del(tmp); if (s1[now].Size()>0) s2[fat].Ins(s1[now].Top()); } if (s2[fat].Size()>=2) { ans=max(ans,s2[fat].Top()+s2[fat].S_Top()); lst.Ins(s2[fat].Top()+s2[fat].S_Top()); } if (s2[fat].Size()>0) ans=max(ans,0); now=fat; }} void Insert(int o){ if (s2[o].Size()>=2) lst.Del(s2[o].Top()+s2[o].S_Top()); s2[o].Ins(0); if (s2[o].Size()>=2) { ans=max(ans,s2[o].Top()+s2[o].S_Top()); lst.Ins(s2[o].Top()+s2[o].S_Top()); } if (s2[o].Size()>0) ans=max(ans,0); int now=o; while (now) { int fat=fa[now]; if (s2[fat].Size()>=2) lst.Del(s2[fat].Top()+s2[fat].S_Top()); int tmp,flag=0; if (s1[now].Size()==0) flag=1; else tmp=s1[now].Top(); s1[now].Ins(dist(o,fat)); if (flag||tmp!=s1[now].Top()) { if (!flag) s2[fat].Del(tmp); s2[fat].Ins(s1[now].Top()); } if (s2[fat].Size()>=2) { lst.Ins(s2[fat].Top()+s2[fat].S_Top()); ans=max(ans,s2[fat].Top()+s2[fat].S_Top()); } if (s2[fat].Size()>0) ans=max(ans,0); now=fat; }} int main(){ memset(h,-1,sizeof h); scanf("%d",&n); F(i,1,n-1) { int a,b; scanf("%d%d",&a,&b); add(a,b);add(b,a); } tag=1; dfs(1,-1); now=inf; size=siz[1]; dfs_rt(1,-1); dfs_dist(rt,-1); tag=0; dfs(rt,-1); tag=1; F(i,1,cnt) c[i][0]=dst[b[i]]; F(i,2,cnt) _log[i]=_log[i>>1]+1; F(j,1,_log[cnt]) for (int i=1;i+(1<
             
              <=cnt;++i) c[i][j]=min(c[i][j-1],c[i+(1<