闲扯
最近有点颓,都修到好晚,早上起来和吔shi一样难受
忍着困意把题面看完,发现啥也不会,又是一场写暴力的模拟赛
T1发现似乎可以DP,顺手码了个
T2像个最小瓶颈路板子,但是只做过N^2算法的...
T3我是真的傻,估计全场就我一人以为只能往前跳于是写了个DP
结果30+35+0
然后发现T1爆了,后面都输出负数，全部用long long 后交了发,居然95?!wtf
后面发现最naiive的贪心都有90,这数据比联赛还水啊,后面发现只有一个点的一次询问答案不一样,打个表就A了
T1 colour
gu
T2 graph
一看就发现这种边就是最小瓶颈路(边),根据最小生成树也是最小瓶颈生成树的性质,我们可以在最小生成树上DFS求到所有点对的最小瓶颈路.
但怎么找符合条件的点对?对于L=0的子任务,我们可以在Kruskal过程中每新加入一条边就计算两个联通块大小的乘积,由于我们的边是从小到大排序的,这条新加入的边一定是这两个联通块点对之间的最小瓶颈路
正解使用了Kruskal重构树,不了解的先去学习一下(我也是做这题才学的)
容易发现,两个原树上的点在重构树上的LCA的点权就是两点间的最小瓶颈路长度,这样只需要求一个LCA的时间复杂度就可以得到两点之间的最小瓶颈路
然后运用启发式合并的思路,我们可以枚举原树上的每一条边计算它的贡献,然后进入重构树上对应点相邻的两棵子树中较小的那一棵枚举点,这样就能得到了两个约束条件:一个是DFS序的约束(因为另一个点必须在另一棵较大的子树中),一个是颜色范围的约束
又转化成并不喜闻乐见的二维数点问题,离线+树状数组+二维前缀和即可
然后发现WA了,xxzh大佬说要注意l=0的情况,改后又RE了,交了几发终于A了...不过跑得好慢
其实这题一开始想线段树合并的,但是没有想到启发式合并,晚上有大佬提供线段树合并的思路就是每个联通块维护权值线段树,Kruskal连一条边的时候,进入较小的块枚举然后在另一棵树上线段树查询
这样的话也是两个log
/* code by RyeCatcher*/inline char gc(){ static char buf[SIZE],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,SIZE,stdin),p1==p2)?EOF:*p1++;}template inline void read(T &x){ x=0;int ne=0;char c; while((c=gc())>'9'||c<'0')ne=c=='-';x=c-48; while((c=gc())>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;return ;}const int maxn=600005;const int inf=0x7fffffff-10;int n,m,l,c[maxn],mx_c=0;struct Nico{ int x,y,dis; bool operator <(const Nico &rhs)const{ return dis =1;x-=x&(-x))tmp+=sum[x];return tmp;}struct QAQ{ int x,y,d,id; bool operator <(const QAQ & rhs)const{ return (x==rhs.x)?id =1&&now<=n){ qwq[++num]=(QAQ){c[now],dfn[now],1,0}; //printf("%d %d\n",dfn[now],c[now]); } return ;}int L,R,LL,RR;void dfs(int now,int id){ int v; if(ch[now][0])dfs(ch[now][0],id); if(ch[now][1])dfs(ch[now][1],id); //LL=max(0,c[now]-l),RR=min(c[now]+l,mx_c); if(now>n||now<1)return ; LL=c[now]-l,RR=c[now]+l;if (!l) RR++; qwq[++num]=(QAQ){-inf-1,L-1,1,id}; qwq[++num]=(QAQ){-inf-1,R,-1,id}; qwq[++num]=(QAQ){LL,L-1,-1,id}; qwq[++num]=(QAQ){LL,R,1,id}; qwq[++num]=(QAQ){RR-1,L-1,1,id}; qwq[++num]=(QAQ){RR-1,R,-1,id}; qwq[++num]=(QAQ){inf,L-1,-1,id}; qwq[++num]=(QAQ){inf,R,1,id}; //printf("%d %d %d %d %d %d\n",now,L,R,LL,RR,id); return ;}int main(){ //freopen("graph19.in","r",stdin); FO(graph); int x,y,z; read(n),read(m),read(l); for(ri i=1;i<=n;i++)pa[i]=i,read(c[i]),mx_c=max(mx_c,c[i]); for(ri i=n+1;i<=n*2+2;i++)pa[i]=i; for(ri i=1;i<=m;i++){ read(x),read(y),read(z); nico[i]=(Nico){x,y,z}; } std::sort(nico+1,nico+1+m); cnt=n; for(ri i=1;i<=m;i++){ x=nico[i].x,y=nico[i].y; x=get(x),y=get(y); if(x==y)continue; pa[x]=++cnt,pa[y]=cnt; fa[x]=cnt,fa[y]=cnt,ch[cnt][0]=x,ch[cnt][1]=y; w[cnt]=nico[i].dis; //printf("%d %d()()()\n",cnt,w[cnt]); if(cnt==2*n-1)break; } fa[cnt]=0; pre_dfs(cnt); //for(ri i=1;i<=cnt;i++)printf("--%d %d %d %d %d %d--\n",i,fa[i],ch[i][0],ch[i][1],dfn[i],ed[i]); for(ri i=n+1;i<=cnt;i++){ x=ch[i][0],y=ch[i][1]; if(size[x]>size[y])std::swap(x,y); L=dfn[y],R=ed[y]; //printf("**%d %d %d %d\n",i,L,R,w[i]); dfs(x,i); } std::sort(qwq+1,qwq+1+num); for(ri i=1;i<=num;i++){ if(qwq[i].id==0){ //printf("%d %d\n",qwq[i].y,qwq[i].d); add(qwq[i].y,1); } else{ //printf("%d %d %lld %d %d\n",qwq[i].id,qwq[i].d,query(qwq[i].y),qwq[i].x,qwq[i].y); qry[qwq[i].id]+=qwq[i].d*query(qwq[i].y); } }//return 0; ll ans=0; //for(ri i=n+1;i<=cnt;i++)printf("&&&%d %d\n",i,w[i]); for(ri i=n+1;i<=cnt;i++){ //printf("%d %d %d\n",i,qry[i],w[i]); ans+=qry[i]*w[i]; } printf("%lld\n",ans); return 0;}