题解 P3761 【[TJOI2017]城市】

好啦首先我们不要被数据范围吓到，常数适宜的情况下3s时限O(n^2)可以信仰过5000，毕竟只是相较1000翻了25倍，如果我们的算法可以在100-120ms内通过1000，就可以凭借信仰过掉这道题 # 本题题解 其实我们发现这道题是可以暴力枚举删那一条边的，这首先有了一个O(N)的复杂度 ，我们接下来要用另一个O(N)处理最远点对的问题 那么删去这条边之后，整棵树将被分为两个联通块 那么此时的最长路有三种来源， 1.两个端点都在联通块1中 2.两个端点都在联通块2中 3.两个端点一个在联通块1，另一个在联通块2 对于1和2我们求一个树上直径即可，对于问题3呢? 我们发现，如果连接了u，v，那么最长路就是 u到联通块1任意一点的最长距离+val+v到联通块2的任意一点最长距离。如果我们适当的选取u和v，使得这两个点的到自己联通块的最长距离最小。那么就是最优的决策了。 也就是说我们要求树上的半径？ #### 树上半径求法 首先我们先做一边树形dp，对于每一个子树，求出经过它的最长链和次长链 然后直径就是枚举每一个点，它的最长链+次长链的最大值 那么半径呢？我们考虑一件事，就是距离它最远的那个点，在它的子树内还是子树外。 如果在子树内，距离就是第一遍dfs求出的最长链，如果在子树外的话，我们在树上在做第二遍dfs，这个dfs额外传一个from参数，from表示这个子树之外的最长链 那么这个最长链from有两个来源 1.它父亲的from+它和父亲的距离 2.它父亲的其他子树中的最长链+他和父亲的距离 对于情况二，如果他就是父亲的所有孩子中的最长链，那么我们的情况2要取次长链，如果不是取最长链就可以了。 然后枚举每个点，半径就是min(max(dp\[i],from\[i]))了 然后只需做4遍一半的dfs即可，代码也是非常的好写 _(小技巧:dfs的时候直接把另一个点打上访问标记即可只dfs一半)_ 上代码~ ```c #include<cstdio> #include<algorithm> using namespace std; const int N=5010;const int INF=0x3f3f3f3f; struct data{int v;int nxt;int val;}edge[2*N]; int alist[N];int cnt;int n; inline void add(int u,int v,int val) {edge[++cnt].v=v;edge[cnt].nxt=alist[u];alist[u]=cnt;edge[cnt].val=val;} int dp[N];int mv[N];int nxdp[N];bool book[N];int rad=INF;int dis;int res=INF; void getd(int x)//求直径 { book[x]=true;int nxt=alist[x]; while(nxt) { int v=edge[nxt].v;int val=edge[nxt].val; if(!book[v]) { getd(v);int va=dp[v]+val;//最长链和次长链 if(va>dp[x]){nxdp[x]=dp[x];dp[x]=va;mv[x]=v;} else if(va>nxdp[x]){nxdp[x]=va;} }nxt=edge[nxt].nxt; }dis=max(dis,dp[x]+nxdp[x]);//更新直径 } void getr(int x,int fr) { rad=min(rad,max(fr,dp[x]));//更新半径 book[x]=false;int nxt=alist[x]; while(nxt) { int v=edge[nxt].v;int val=edge[nxt].val; if(book[v])//更新fr，记得特判自己就是最长链的情况 { if(v==mv[x]){getr(v,max(nxdp[x]+val,fr+val));} else {getr(v,max(dp[x]+val,fr+val));} }nxt=edge[nxt].nxt; } }//清空dp的函数 inline void clear(){for(int i=1;i<=n;i++){dp[i]=mv[i]=nxdp[i]=book[i]=0;}rad=INF;dis=0;} int u[N];int v[N];int val[N]; int main() { scanf("%d",&n); for(int i=1;i<n;i++)//读进来 { scanf("%d%d%d",&u[i],&v[i],&val[i]); add(u[i],v[i],val[i]);add(v[i],u[i],val[i]); } for(int i=1;i<n;i++)//枚举边 { int d1;int d2;int r1;int r2; book[v[i]]=1;getd(u[i]);d1=dis;//求直径 dis=0;getd(v[i]);d2=dis;//求半径 book[v[i]]=0;getr(u[i],0);r1=rad;//求直径 rad=INF;getr(v[i],0);r2=rad;//求半径 res=min(res,max(max(d1,d2),r1+r2+val[i]));//更新答案 clear();//不要忘记清空 } printf("%d",res);return 0;//拜拜程序~ } ```