题解 【P4775 [NOI2018] 情报中心】

本大胖题的阳间做法，不用分类讨论了！ **题意** ：给出一棵 $n$ 个点的树，边有正边权。 给出树上的 $m$ 条路径，每条路径有一个花费。 选出两条路径，使得两条路径至少有一条公共边，且两条路径的**并**的边权和减去花费和最大。或指出不存在满足要求的方案。 多组数据，$n\leq 5\times 10^4,m\leq 10^5,\sum n\leq 10^6,\sum m\leq 2\times 10^6$。时限$\texttt{8s}$。 ------------ 对于给出的花费为 $w$ 的路径 $(u,v)$ ，我们记 $c_{(u,v)}=dis(u,v)-2w$。  可能的两种合法方案如图。对于两种情况，收益**的两倍**均为 ： $$c_{(u_1,v_1)}+c_{(u_2,v_2)}+dis(u_1,u_2)+dis(v_1,v_2)$$ 考虑枚举 $t={\rm lca}(u_1,u_2)$ （即相交部分最深的点） 然后求出最大的 $$c_{(u_1,v_1)}+c_{(u_2,v_2)}+dep_{u_1}+dep_{u_2}+dis(v_1,v_2)$$ 还要加上此时确定的 $-2dep_{{\rm lca}(u_1,u_2)}$。 这可以看做将 $v_1$ 的权值定为 $w_{v_1}=c_{(u_1,v_1)}+dep_{u_1}$ ，而 $v_2$ 的权值定为 $w_{v_2}=c_{(u_2,v_2)}+dep_{u_2}$。 选择 $v_1,v_2$ 两者配对的贡献为 $w_{v_1}+w_{v_2}+dis(v_1,v_2)$。 这是经典的树上（带权）最远点对问题，有结论 ： - 记 ${\rm diam}(S)$ 为树上点集 $S$ 的最远点对。 对于 $S=S_1∪S_2$ ，有 ${\rm diam}(S)={\rm diam}\big({\rm diam}(S_1)∪{\rm diam}(S_2)\big)$ 可见 [P2056 [ZJOI2007]捉迷藏](https://www.luogu.com.cn/problem/P2056)。 利用这个结论，只需计算 $O(1)$ 次两点距离，就能合并点集最远点对，或者计算两个点集之间的最远点对。 使用 $O(1)\ \rm LCA$ ，这个复杂度就是 $O(1)$。 记 $S_u$ 为子树内的路径提供的匹配候选点集。 对于 $t$ ，要计算 $t$ 的各个子分支之间的贡献。 对于路径 $(u,v)$ ，记 $t={\rm lca}(u,v)$。则 $u$ 会出现在 $S_{[v\rightarrow t)}$ 中， $v$ 会出现在 $S_{[u\rightarrow t)}$ 中。 它们不能出现在 $t$ 的祖先的 $S$ 中，否则会产生错误的匹配。 使用树上差分，我们在 $u$ 点加入，在 $u$ 到 $t$ 的路径上的倒数第二个点删除。 用线段树合并维护，在合并时即可获得不同子分支之间的贡献。 复杂度 $O\big((n+m)\log n\big)$。 不到 $\rm 4Kb$ 的代码 ： ```cpp #include<algorithm> #include<cstring> #include<cstdio> #include<vector> #define pb push_back #define ll long long #define MaxN 50050 #define MaxM 100500 using namespace std; const ll INF=1ll<<60; vector<int> g[MaxN],l[MaxN]; int dep[MaxN],f[16][MaxN] ,dfn[MaxN],out[MaxN],id[MaxN<<1],tim; ll dist[MaxN]; void pfs(int u) { id[dfn[u]=++tim]=u; for (int i=0,v;i<g[u].size();i++) if (!dfn[v=g[u][i]]){ dep[v]=dep[f[0][v]=u]+1; dist[v]=dist[u]+l[u][i]; pfs(v);id[++tim]=u; } out[u]=tim; } #define Pii pair<int,int> #define Pr pair<int,ll> #define fir first #define sec second #define mp make_pair int lg2[MaxN<<1]; Pii t[18][MaxN<<1]; void Init() { for (int i=2;i<=tim;i++)lg2[i]=lg2[i>>1]+1; for (int i=1;i<=tim;i++)t[0][i]=mp(dep[id[i]],id[i]); for (int j=1;(1<<j)<=tim;j++) for (int i=1;i+(1<<j)-1<=tim;i++) t[j][i]=min(t[j-1][i],t[j-1][i+(1<<(j-1))]); } int lca(int u,int v){ u=dfn[u];v=dfn[v];if (u>v)swap(u,v); int k=lg2[v-u+1]; return min(t[k][u],t[k][v-(1<<k)+1]).second; } int up(int u,int t){ int k=15; while(k--)while(dep[f[k][u]]>dep[t])u=f[k][u]; return u; } ll dis(int u,int v) {return dist[u]+dist[v]-2*dist[lca(u,v)];} inline ll dis(Pr u,Pr v) {return dis(u.fir,v.fir)+u.sec+v.sec;} struct Data{Pr u,v;}Z; ll merge(Data &S,const Data &A,const Data &B) { if (!A.u.fir&&!A.v.fir){S=B;return -INF;} if (!B.u.fir&&!B.v.fir){S=A;return -INF;} ll ret,mx=-INF,s;int op=-1; #define chk(u,v,w) if (u.fir&&v.fir){s=dis(u,v);if (s>mx){mx=s;op=w;}} chk(A.u,B.u,3);chk(A.u,B.v,4); chk(A.v,B.u,5);chk(A.v,B.v,6); ret=mx; chk(A.u,A.v,1);chk(B.u,B.v,2); if (op==1)S=A;if (op==2)S=B; if (op==3)S=(Data){A.u,B.u};if (op==4)S=(Data){A.u,B.v}; if (op==5)S=(Data){A.v,B.u};if (op==6)S=(Data){A.v,B.v}; return ret; } struct Node{int l,r;Data x;}a[MaxM*40]; int rt[MaxN],tn,to;Pr wfc; void up(int u){ if (!a[u].l||!a[u].r){a[u].x=a[a[u].l|a[u].r].x;return ;} merge(a[u].x,a[a[u].l].x,a[a[u].r].x); } void add(int l,int r,int &u) { if (!u)u=++tn; if (l==r){a[u].x.u=wfc;return ;} int mid=(l+r)>>1; if (to<=mid)add(l,mid,a[u].l); else add(mid+1,r,a[u].r); up(u); } void del(int l,int r,int &u) { if (l==r){a[u].x.u=mp(0,0);return ;} int mid=(l+r)>>1; if (to<=mid)del(l,mid,a[u].l); else del(mid+1,r,a[u].r); up(u); } int merge(int u,int v) { if (!u||!v)return u|v; merge(a[u].x,a[u].x,a[v].x); a[u].l=merge(a[u].l,a[v].l); a[u].r=merge(a[u].r,a[v].r); return u; } ll ans; vector<int> b[MaxN]; int n,m; void dfs(int u) { for (int i=0,v;i<g[u].size();i++) if (dep[v=g[u][i]]>dep[u]){ dfs(v); ans=max(ans,merge(Z,a[rt[u]].x,a[rt[v]].x)-2*dist[u]); rt[u]=merge(rt[u],rt[v]); } for (int i=0;i<b[u].size();i++) {to=b[u][i];del(1,m,rt[u]);} } void solve() { scanf("%d",&n); for (int i=1,u,v,w;i<n;i++){ scanf("%d%d%d",&u,&v,&w); g[u].pb(v);l[u].pb(w); g[v].pb(u);l[v].pb(w); }dep[1]=1;pfs(1);Init(); for (int j=1;j<15;j++) for (int i=1;i<=n;i++) f[j][i]=f[j-1][f[j-1][i]]; scanf("%d",&m); ans=-INF; for (int i=1;i<=m;i++){ int u,v;ll w; scanf("%d%d%lld",&u,&v,&w); if (u==v)continue; w=dis(u,v)-2*w; int t=lca(u,v),tu=up(u,t),tv=up(v,t); to=i; if (u!=t){ wfc=mp(v,w+dist[u]); ans=max(ans,merge(Z,(Data){wfc,mp(0,0)},a[rt[u]].x)-2*dist[u]); add(1,m,rt[u]);b[tu].pb(i); } if (v!=t){ wfc=mp(u,w+dist[v]); ans=max(ans,merge(Z,(Data){wfc,mp(0,0)},a[rt[v]].x)-2*dist[v]); add(1,m,rt[v]);b[tv].pb(i); } } dfs(1); if (ans<=-INF/10)puts("F"); else printf("%lld\n",ans/2); for (int i=1;i<=n;i++){ g[i].clear();l[i].clear();b[i].clear(); dfn[i]=rt[i]=0; }memset(a,0,sizeof(Node)*(tn+5));tn=tim=0; } int main() { int T;scanf("%d",&T); while(T--)solve(); return 0; } ``` 所以，2018 年最难题还应该是 D2T3 (