题意:
给出一棵树,支持以下操作:
选择树上2个叶子节点,把这2个节点加到答案里,同时删除其中一个节点。
询问怎么操作使得答案最大。
题解:
结论:维护一条直径,除直径以外的点对答案的贡献是max(dis(i,x),dis(i,y))。
直径端点的求解方法:
先一遍搜索出最深的点,那么这个点一定是端点之一。
再以这个点为根再搜一遍,搜到最深的点是端点之二。
距离求解套一个倍增LCA即可。
由于要输出方案,必须遍历直径,对直径上的每一个点递归搜它们的子树,这里处理的比较麻烦。(因为每一步操作删除的点必须满足在当前树形下是叶子)
#include<bits/stdc++.h> using namespace std; const int maxn=2e5+100; int n; vector<int> g[maxn]; int d[maxn],x,y,tx,ty,ttx,tty,father[30][maxn],h[maxn]; long long ans; int vis[maxn]; vector<pair<pair<int,int>, int > > Ans; void dfs1 (int x,int f) { d[x]=d[f]+1; for (int y:g[x]) if (y!=f) dfs1(y,x); } void dfs (int x) { for (int y:g[x]) { if (y==father[0][x]) continue; h[y]=h[x]+1; father[0][y]=x; dfs(y); } } int lca (int x,int y) { if (h[x]<h[y]) swap(x,y); for (int i=20;i>=0;i--) if (h[x]-h[y]>>i) x=father[i][x]; if (x==y) return x; for (int i=20;i>=0;i--) if (father[i][x]!=father[i][y]) x=father[i][x],y=father[i][y]; return father[0][x]; } int getDis (int x,int y) { return h[x]+h[y]-h[lca(x,y)]*2; } void dfs2 (int u) { if (!vis[u]) vis[u]=2; for (int v:g[u]) { if (vis[v]) continue; dfs2(v); } if (vis[u]==1) return; vis[u]=2; int dx=getDis(u,tx); int dy=getDis(u,ty); if (dx>dy) { ans+=dx; Ans.push_back(make_pair(make_pair(u,tx),u)); } else { ans+=dy; Ans.push_back(make_pair(make_pair(u,ty),u)); } } int main () { scanf("%d",&n); for (int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); g[x].push_back(y); g[y].push_back(x); } dfs1(1,0); for (int i=1;i<=n;i++) { if (d[i]>d[x]) { x=i; } } for (int i=0;i<=n;i++) d[i]=0; dfs1(x,0); for (int i=1;i<=n;i++) { if (d[i]>d[y]) { y=i; } } dfs(1);//倍增LCA for (int i=1;i<=20;i++) for (int j=1;j<=n;j++) father[i][j]=father[i-1][father[i-1][j]]; tx=x,ty=y,ttx=x,tty=y; while (h[x]>h[y]) { vis[x]=1; x=father[0][x]; } while (h[y]>h[x]) { vis[y]=1; y=father[0][y]; } while (x!=y) { vis[x]=1; vis[y]=1; x=father[0][x]; y=father[0][y]; } vis[x]=1; while (h[ttx]>h[tty]) { dfs2(ttx); ttx=father[0][ttx]; } while (h[tty]>h[ttx]) { dfs2(tty); tty=father[0][tty]; } while (ttx!=tty) { dfs2(ttx); dfs2(tty); ttx=father[0][ttx]; tty=father[0][tty]; } dfs2(ttx); //printf("%d\n",getDis(tx,ty)); ans+=1ll*getDis(tx,ty)*(getDis(tx,ty)+1)/2; int Lca=lca(tx,ty); while (tx!=Lca) { int z=tx; tx=father[0][tx]; Ans.push_back(make_pair(make_pair(z,ty),z)); } while (ty!=Lca) { int z=ty; ty=father[0][ty]; Ans.push_back(make_pair(make_pair(z,Lca),z)); } printf("%lld\n",ans); for (auto i:Ans) printf("%d %d %d\n",i.first.first,i.first.second,i.second); }