题目概述

有一棵带边权的树，询问 $m$ 次，每次新建一条边权为 $x$ 的边（不能建重边），问如何建使得 $1$ 到 $n$ 的最短路最大。

解题报告

可能不难吧，主要是需要比较显然的贪心来挖掘出性质（而且不要看错题目）。

把 $1$ 到 $n$ 的路径拿出来，如果途中有节点除了路径上的点之外还有直接或间接连接了至少 $2$ 个节点，那么我们肯定把新的边连接到那些点上去，这样不影响 $1$ 到 $n$ 的路径，最短路就是原来的距离。

排除了这种情况之后，$1$ 到 $n$ 路径上的点最多只会连出去 $1$ 个点，就可以直接瞎搞了。我们需要求的是 $min\{max\{dis_{1,u}+x+dis_{v,n}|(u,v)\not\in E\},dis_{1,n}\}$ ，会发现不管 $x$ 怎么样最优的 $(u,v)$ 不变，所以处理出 $(u,v)$ 就行了。

示例程序

其实只需要记一下最大和次大，我太懒了直接用了个setXD。

#include<cstdio>
#include<algorithm>
#include<set>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long long LL;
const int maxn=300000;

int n,te,fa[maxn+5],si[maxn+5];LL dis[maxn+5],ans;bool vis[maxn+5],orz;
int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5],w[(maxn<<1)+5];
set< pair<LL,int> > S;set< pair<LL,int> >::iterator it;

#define Add(x,y,z) (son[++E]=(y),w[E]=(z),nxt[E]=lnk[x],lnk[x]=E)
void getfa(int x,int pre=0){
    for (int j=(fa[x]=pre,si[x]=1,lnk[x]);j;j=nxt[j])
        if (son[j]!=pre) getfa(son[j],x),si[x]+=si[son[j]];
}
void getdis(int x,int pre=0,LL now=0){
    for (int j=(dis[x]=now,lnk[x]);j;j=nxt[j])
        if (son[j]!=pre) getdis(son[j],x,now+w[j]);
}
inline void Fix(int x,int pre,LL now){
    if (S.size()){
        if ((it=S.begin(),(*it).sc)!=pre) ans=max(ans,dis[x]-(*it).fr);
        else {it++;if (it!=S.end()) ans=max(ans,dis[x]-(*it).fr);}
    }S.insert(mp(-now,x));
}
void getans(int x,int pre=0,LL now=0){
    Fix(x,pre,now);for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre&&!vis[son[j]]) Fix(son[j],x,now+w[j]);
    for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre&&vis[son[j]]) getans(son[j],x,now+w[j]);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&te);for (int i=1,x,y,z;i<n;i++) scanf("%d%d%d",&x,&y,&z),Add(x,y,z),Add(y,x,z);
    getfa(1);for (int x=n,lst=0;x;lst=x,x=fa[x]) {vis[x]=true;if (lst&&si[x]-si[lst]>2) {orz=true;break;}}
    getdis(n);if (!orz) getans(1); else {for (int i=1;i<=te;i++) printf("%lld\n",dis[1]);return 0;}
    for (int x;te;te--) scanf("%d",&x),printf("%lld\n",min(dis[1],ans+x));return 0;
}