题解 P3714 【[BJOI2017]树的难题】

听说这种题叫单调队列按秩合并？ zz的我不会写bfs强行dfs一波结果产生了一个用了单调队列却还是两个log的\**做法…… __________________ ## 本题题解 ### 前置知识:点分治 不会点分治或者不知道点分治是啥的就还是出门左转模板区吧 ____________________ 简单复述一下题目内容 求树上长度在l,r之间并且权值最大的路径，路径的权值定义为每一段同色段贡献一个自己颜色的权值(边上有颜色) 如这个路径长成这样 红红黑红红 那么权值就是2倍红色权值+1倍黑色权值 ____________ 然而事实上一看长度在l到r这个路径长度限制几乎就只有点分治可以做这道题了 **所以对树T进行点分治考虑过当前分治中心G的所有路径** 那么我们发现可以大力dfs一波G到当前联通块中所有点的路径 然后处理出这些路径的权值来 现在我们唯一要做的就是“拼合两条路径” 再具体点就是对于每一条路径求出一条最优的和他匹配的路径 然后你发现一个十分遗憾的事实是 **两条路径拼起来的权值不一定等于这两条路径的权值之和** 然后你又发现一个有趣的事实是 **如果两条路径最顶上那条边(和G相邻的那条边)颜色不同，那么上面的结论还是对的，如果颜色一样，减去一次本颜色的权值就行了** 另一个事实是 **如果两条路径顶上的颜色不一样，那么两个路径不会在同一个子树当中** 因此我们可以先将切掉中心之后剩下的所有联通块按照他们和G连边的颜色排序(这里排序的目的是将相同颜色的联通块方程放到一个区间里,颜色之间的顺序并不做要求) 然后依次dfs每一组颜色相同的联通块 对于拎出来的这些路径将他们按照路径长度排序 此时我们在这个序列上从左到右扫一遍，对于每一个路径求出一个最优的和它颜色不同同的路径和它匹配起来 那么我们发现如果这个路径的长度是$len$那么待选路径长度的取值范围就是 $[max(l-len,0),min(mx,r-len)]$ mx的意义一会再讲(现在说的话就是所有待选路径中长度的最大值) 然后由于我们把路径按照len排序了，所以长度取值范围的左端点和右端点也是单调移动的，此时我们可以使用单调队列求出待匹配路径区间的最大权值了也就达到了对于每一个路径求出权值最大的异色匹配路径的目的了 当这个颜色全部跑完单调队列之后我们将这些路径全部插入到权值数组当中，同事更新一下mx的值，然后接着去做下一种颜色 这样的话对于一组路径$i,j$会在颜色较大的那一头被统计一次，同时也规避了同一子联通块中的路径相互匹配的情况 接下来我们考虑对每一个路径求出权值最大的同色匹配路径，当然和异色路径的套路差不多，我们在每一个颜色里面按照所在子联通块的编号排序，然后依然使用单调队列对每一个路径求出一个和他匹配的最优的同色路径之后给答案去取一个max 然后做完了？ **不，你的算法是假的可以叉成$O(n^2)$** 仔细回想，单调队列的均摊复杂度的确是$O(1)$但是我们可能忽略了一个十分重要的事实是单调队列是有初始化复杂度的 因此我们认真分析一次点分治的复杂度 对于求异色路径匹配的过程其实没有什么区别 我们单调队列进行操作的复杂度是$O(n)$的，但是每次初始化的复杂度是$O(mx)$的，mx为候选路径中的最深值，那么假如我们构造一个树使得你第一次就撞上了所有路径中最深的路径，那么你每一次点分治的复杂度将会是$O(n^2)$然后你的程序就被叉掉了 正确的做法是排序时比较颜色的时候，比较的是这个颜色中最深的路径值，尽量将深度较深路径放在后边，而在颜色内部排序的时候，按照子树中最深的路径进行排序，也是尽量的把深的路径所在的联通块放在后面 这样的话每次初始化的复杂度$O(mx)$是和这个子联通块的size同阶的(因为在此之前没有路径比这个联通块中的最深路径的深度大)，所以总的初始化复杂度迅速降低至整个当前分治的联通块的点数 这个技巧似乎被某些人成为单调队列按秩合并？ 如果我们使用基数排序或者bfs来给路径按长度排序的话，我们的每一轮分治的复杂度就是$O(dlogd+size)$d是分治中心的度数，size是所分治联通块的点数 总复杂度是可爱的$O(nlogn)$ 如果你是一个像我一样的zz不会bfs，强行sort一波给所有路径排序的话 复杂度就是zz的$O(nlog^2n)$了 上代码~ ```C // luogu-judger-enable-o2 #include<cstdio> #include<algorithm> using namespace std;const int N=2*1e5+10;typedef long long ll; int n;int m;int v[2*N];int x[2*N];int ct;int al[N];int cl[2*N];int L;int R; int cd[N];int ud[N];int dep[N];ll dis[N];int tp;ll w[N];ll res; struct data//对路径按照各种关键字反复排序 { ll val;int dep;int col;int u; inline friend bool operator <(data a,data b) {return (a.col==b.col)?a.dep>b.dep:(cd[a.col]==cd[b.col])?a.col<b.col:cd[a.col]<cd[b.col];} }a[N]; inline bool cmp1(const data& a,const data& b) {return (a.u==b.u)?a.dep>b.dep:((ud[a.u]==ud[b.u])?a.u<b.u:ud[a.u]<ud[b.u]);} inline void add(int u,int V,int c){v[++ct]=V;x[ct]=al[u];al[u]=ct;cl[ct]=c;} bool cut[N];bool book[N];int siz[N];ll dw[N];int q[N];int hd;int tl; inline int dfs1(int u)//siz { book[u]=true; for(int i=al[u];i;i=x[i])if(!book[v[i]]&&!cut[v[i]])siz[u]+=dfs1(v[i]); book[u]=false;return siz[u]; } inline int find(int u,const int& tot)//重心 { book[u]=true;int ret=u; for(int i=al[u];i;i=x[i]) if(!book[v[i]]&&!cut[v[i]]&&2*siz[v[i]]>=tot){ret=find(v[i],tot);break;} book[u]=false;return ret; } inline void dfs3(int u,int Col,const int& t,const int& crl)//把路径拉出来 { book[u]=true;a[++tp]=(data){dis[u],dep[u],crl,t}; for(int i=al[u];i;i=x[i]) if(!book[v[i]]&&!cut[v[i]]) { dep[v[i]]=dep[u]+1;dis[v[i]]=dis[u]+((Col==cl[i])?0:w[cl[i]]); dfs3(v[i],cl[i],t,crl); }book[u]=false;siz[u]=1; } inline void solve(int u)//大力点分治 { dfs1(u);int g=find(u,siz[u]);cut[g]=true;if(siz[u]==1)return;tp=0; for(int i=al[g];i;i=x[i]) if(!cut[v[i]]){dep[v[i]]=1;dis[v[i]]=w[cl[i]];dfs3(v[i],cl[i],v[i],cl[i]);} for(int i=1;i<=tp;++i)cd[a[i].col]=max(cd[a[i].col],a[i].dep),ud[a[i].u]=max(ud[a[i].u],a[i].dep); for(int i=1;i<=tp;++i)if(L<=a[i].dep&&a[i].dep<=R)res=max(res,a[i].val); sort(a+1,a+tp+1); int lst=1;int mxd=0;hd=1;tl=0;int nr=0;a[0].col=a[1].col; for(int i=1;i<=tp;++i)//跑单调队列 { if(a[i].col!=a[i-1].col) { hd=1;tl=0;nr=0; for(int j=lst;j<i;++j)dw[a[j].dep]=max(dw[a[j].dep],a[j].val),mxd=max(mxd,a[j].dep);lst=i; } int dr=min(mxd,max(R-a[i].dep,0));int dl=min(mxd,max(L-a[i].dep,0));if(dl>=dr){continue;} for(int np=nr+1;np<=dr;++np) {while(hd<=tl&&dw[q[tl]]<dw[np])--tl;q[++tl]=np;}nr=dr; while(hd<=tl&&q[hd]<dl)++hd;if(hd<=tl)res=max(res,dw[q[hd]]+a[i].val); } for(int i=1;i<=tp;++i)dw[a[i].dep]=-0x7f7f7f7f; lst=1;hd=1;tl=0;nr=0;mxd=0;int lst2=1; for(int t=1;t<=tp+1;++t) if(a[t].col!=a[t-1].col) { sort(a+lst,a+t,cmp1); for(int i=lst;i<t;++i) { if(a[i].u!=a[i-1].u) { hd=1;tl=0;nr=0; for(int j=lst;j<i;j++)dw[a[j].dep]=max(dw[a[j].dep],a[j].val),mxd=max(mxd,a[j].dep);lst2=i; } int dr=min(mxd,max(R-a[i].dep,0));int dl=min(mxd,max(L-a[i].dep,0));if(dl>=dr)continue; for(int np=nr+1;np<=dr;++np) {while(hd<=tl&&dw[q[tl]]<dw[np])--tl;q[++tl]=np;}nr=dr; while(hd<=tl&&q[hd]<dl)++hd;if(hd<=tl)res=max(res,dw[q[hd]]+a[i].val-w[a[i].col]); }hd=1;tl=0;nr=0;mxd=0; for(int i=lst;i<t;++i)dw[a[i].dep]=-0x7f7f7f7f;lst=t; } for(int i=1;i<=tp;++i)cd[a[i].col]=0,ud[a[i].u]=0; for(int i=al[g];i;i=x[i])if(!cut[v[i]])solve(v[i]); } int main() { scanf("%d%d%d%d",&n,&m,&L,&R);res=-0x7f7f7f7f; for(int i=1;i<=m;i++)scanf("%lld",&w[i]); for(int i=1;i<=n;i++)siz[i]=1;for(int i=0;i<=n;i++)dw[i]=-0x7f7f7f7f; for(int i=1,u,v,w;i<n;i++){scanf("%d%d%d",&u,&v,&w);add(u,v,w);add(v,u,w);} solve(1);printf("%lld",res);return 0;//拜拜程序~ } ```