题目描述
给你一棵 n 个点的无根树.
树上的每条边具有颜色. 一共有 m 种颜色, 编号为 1 到 m. 第 i 种颜色的权值为 ci.
对于一条树上的简单路径, 路径上经过的所有边按顺序组成一个颜色序列, 序列可以划
分成若干个相同颜色段. 定义路径权值为颜色序列上每个同颜色段的颜色权值之和.
请你计算, 经过边数在 l 到 r 之间的所有简单路径中, 路径权值的最大值.
题解
如果没有颜色这种东西的话, 看到 l~r 的限制, 就容易想到点分治 + 单调队列维护.
我们的单调队列的作用其实就是合并两颗子树.
考虑有如果我们准备合并的那两颗子树的第一条边颜色相同, 那么答案应当再去减去一个边权.
所以我们得对于每种颜色分别维护.
但是我们还需要保证合并的复杂度.
这时候我们考虑对于颜色相同的子树, 我们把它们放在一起按照最大深度从小到大处理, 这样能够保证它的复杂度是线性的.
但是多个颜色怎么处理.
观察到我们合并两个不同的颜色可以看做是两个桶在合并, 所以对于颜色我们按照这个颜色的最大深度排个序就好了.
代码
我要再把 while 写成 if 就去 cs.
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<queue>
- #include<algorithm>
- #define N 200002
- using namespace std;
- int head[N],tot,h,t,q[N],dp[N],size[N],root,sum,deep[N],maxdeep,su[N];
- int maxl,minl,que[N],colmaxdeep[N],n,m,cal[N],ans,c[N];
- bool vis[N],visit[N];
- inline int rd(){
- int x=0;char c=getchar();bool f=0;
- while(!isdigit(c)){if(c=='-')f=1;c=getchar();}
- while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
- return f?-x:x;
- }
- struct edge{int n,to,l;}e[N<<1];
- struct node{
- int id,col,dep;
- inline bool operator <(const node &b)const{
- if(col!=b.col){
- // if(su[col]!=su[b.col])return su[col]<su[b.col];
- if(colmaxdeep[col]!=colmaxdeep[b.col])return colmaxdeep[col]<colmaxdeep[b.col];
- else return col<b.col;
- }
- else return dep<b.dep;
- }
- }b[N];
- int tong[N],_tong[N];
- inline void add(int u,int v,int l){
- e[++tot].n=head[u];e[tot].to=v;head[u]=tot;e[tot].l=l;
- }
- void getroot(int u,int fa){
- dp[u]=0;size[u]=1;
- for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa&&!vis[e[i].to]){
- int v=e[i].to;
- getroot(v,u);
- size[u]+=size[v];
- dp[u]=max(dp[u],size[v]);
- }
- dp[u]=max(dp[u],sum-size[u]);
- if(dp[u]<dp[root])root=u;
- }
- void getsize(int u,int fa){
- size[u]=1;
- for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa&&!vis[e[i].to]){
- int v=e[i].to;
- getsize(v,u);
- size[u]+=size[v];
- }
- }
- void getdeep(int u,int fa,int val,int lastcol){
- cal[u]=val;maxdeep=max(maxdeep,deep[u]);
- for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa&&!vis[e[i].to]){
- int v=e[i].to;deep[v]=deep[u]+1;
- getdeep(v,u,e[i].l==lastcol?val:val+c[e[i].l],e[i].l);
- }
- }
- void getcalc(int u,int fa){
- tong[deep[u]]=max(tong[deep[u]],cal[u]);
- for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa&&!vis[e[i].to]){
- int v=e[i].to;deep[v]=deep[u]+1;
- getcalc(v,u);
- }
- }
- inline void _ins(int x){
- while(h<=t&&_tong[q[t]]<=_tong[x])t--;
- q[++t]=x;
- }
- inline void ins(int x){
- while(h<=t&&tong[q[t]]<=tong[x])t--;
- q[++t]=x;
- }
- inline void calc(int u){
- int clsum=0;vis[u]=1;
- for(int i=head[u];i;i=e[i].n)if(!vis[e[i].to]){
- int v=e[i].to;maxdeep=0;
- deep[v]=1;getdeep(v,u,c[e[i].l],e[i].l);
- b[++clsum]=node{v,e[i].l,maxdeep};
- colmaxdeep[e[i].l]=maxdeep;su[e[i].l]++;
- }
- int nowmaxdeep=0,summaxdeep=0;
- sort(b+1,b+clsum+1);
- for(int o=1;o<=clsum+1;++o){
- int v=b[o].id;
- if(b[o].col!=b[o-1].col){
- summaxdeep=max(summaxdeep,nowmaxdeep);
- h=t=1;q[h]=0;int p=0;
- for(int i=nowmaxdeep;i>=1;--i){
- while(p+i<maxl&&p<summaxdeep){p++;_ins(p);}
- while(h<=t&&q[h]+i<minl)h++;if(h<=t)ans=max(ans,tong[i]+_tong[q[h]]);
- }
- for(int j=1;j<=nowmaxdeep;++j)_tong[j]=max(_tong[j],tong[j]),tong[j]=-1e9;
- nowmaxdeep=0;
- }
- if(o>clsum)break;
- q[h=t=1]=v;visit[v]=1;que[0]=0;
- while(h<=t){
- int u=q[h++];
- que[++que[0]]=u;
- for(int i=head[u];i;i=e[i].n){
- int v=e[i].to;
- if(!vis[v]&&!visit[v])q[++t]=v,visit[v]=1;
- }
- }
- h=1;t=0;int p=0;
- for(int i=que[0];i>=1;--i){
- int x=que[i];visit[x]=0;
- while(p+deep[x]<maxl&&p<nowmaxdeep){p++;ins(p);}
- while(h<=t&&q[h]+deep[x]<minl)h++;
- if(h<=t)ans=max(ans,cal[x]+tong[q[h]]-c[b[o].col]);
- }
- getcalc(v,u);
- nowmaxdeep=max(nowmaxdeep,b[o].dep);
- }
- for(int i=head[u];i;i=e[i].n)if(!vis[e[i].to])colmaxdeep[e[i].l]=0,su[e[i].l]=0;
- // cout<<summaxdeep<<endl;
- for(int i=1;i<=summaxdeep;++i)tong[i]=_tong[i]=-1e9;
- }
- void solve(int u){
- calc(u);
- for(int i=head[u];i;i=e[i].n)if(!vis[e[i].to]){
- int v=e[i].to;
- root=n+1;sum=size[v];
- getroot(v,u);getsize(root,0);
- solve(root);
- }
- }
- int main(){
- n=rd();m=rd();minl=rd();maxl=rd();
- for(int i=1;i<=n;++i)tong[i]=_tong[i]=-1e9;
- ans=-1e9;
- for(int i=1;i<=m;++i)c[i]=rd();
- int u,v,w;
- for(int i=1;i<n;++i){
- u=rd();v=rd();w=rd();
- add(u,v,w);add(v,u,w);
- }
- sum=n;root=n+1;dp[root]=n+1;
- getroot(1,0);getsize(root,0);
- solve(root);
- printf("%d\n",ans);
- return 0;
- }
[BJOI2017] 树的难题
来源: http://www.bubuko.com/infodetail-2987119.html