欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

特教的理性愉悦(ecstasy)

程序员文章站 2022-06-02 12:39:00
...

特教的理性愉悦(ecstasy)
特教的理性愉悦(ecstasy)


【分析】
来二中的又一道图论题,貌似还是2016noi导刊的一套题。。。

从题面开始分析,这明显是一道图论题,而且还是一道LCA的题目,或者是和LCA有关的一道题。但在询问过程中两个点之间未必联通,貌似无法直接用LCA算法求出(u,v)的路径。仔细思考树的一些特性我们会发现,如果在不走回头路的情形下,树中两点之间的路径唯一的。换言之如果(u,v)联通,那么当前两点间的路径和建树完全后两点间的距离是一样的。

具体上,我们先将所有所有操作存起来,建成一棵树并完成LCA的预处理(本题使用的是简单直观的倍增算法)。然后我们重新枚举操作,并用并查集维护操作1和判断(u,v)是否在同一棵树中(也就是同一个集合)。碰到操作2,如果不在同一集合就直接输出-1;否则找到(u,v)的LCA,沿着路径走一遍就能得到正解。(这里有一个规律可以推导,距离和=sigma(n+1-i)*i*wi,n为路径中边的总数,wi为每条边的权值)

单次操作在最坏情形下的时间复杂度为O(n),总的复杂度为O(n*m)。也就是50分的做法。

这里面的m是不能再减小了,只能从n处入手,改变直接枚举整条路径这种方式来换取更小的时间复杂度。比较容易想到的是利用预处理和前缀和来优化时间。我的思路从这里无法再延伸了,最终还是只能在考场上敲出五十分的解法(其中还因为忘记开longlong而WA了两个点)。考后试题讲解中一位大佬的算法给了我很多启迪:他是这样说的,我们虽然无法直接用简单的一位前缀和求出路径的权值,但我们能动用一些数学方法,预处理出高阶前缀,通过一些神奇的运算在O(1)的时间内算出答案。

观察原来那个sigma式子,我们发现从u或v任意一端枚举所得的结果是不变的。我们可以分别求出从u到LCA的权值和从v到LCA的权值。仔细观察可以发现,两个因数的大小都与深度有关。
盗用一下某位博主的一张图(这里边6-7的系数标错了应该是6*2):
特教的理性愉悦(ecstasy)
(如果这篇blog看不懂也可光临一下他的博客,逃)

其中一个数随点深度的增加而递减。用ndis表示从深度的负数乘上边的权值(这里边的权值可以下沉到它下端的点上,方便计算)。为了防止溢出我们改为总数n减去深度再乘上他的边权(或者是点权?,雾),接下来计算的操作中你将会看到n被完全消掉。

我们先用ndis[x]-ndis[lca]发现求到的全是负数,而且貌似递减的顺序不太对(雾)。别担心这时候应该再减去(n-dep[x])*(dis[lca]-dis[x])。我们惊异的发现不仅原来的n被全消掉了,而且变成了一个从x出发的系数成等差序列递增的值的和。同理我们也可以求出y的部分。

五十分代码如下:

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+1000;
const int M=3e5;
int f[N];
struct Opt{
    int x,y,w,k;
}opt[M];
struct Edge{
    int v,c,nxt;
}edge[N<<1];
int head[N],tot=0;

int n,m,large,s=1;
int d[N],p[N][20],val[N];
void add_edge(int x,int y,int c){
    edge[tot].v=y;
    edge[tot].c=c;
    edge[tot].nxt=head[x];
    head[x]=tot++;
    return ;
}
void dfs(int u,int dep){
    d[u]=dep;
    for(int i=head[u];i!=-1;i=edge[i].nxt){
        int v=edge[i].v;
        if(!d[v]){
            p[v][0]=u;
            val[v]=edge[i].c;
            dfs(v,dep+1);
        }
    }
}
void init_lca(){
    dfs(s,1);
    p[s][0]=s;
    large=0;
    while(1<<large<=n)large++;
    large--;
    for(int j=1;j<=large;j++)
        for(int i=1;i<=n;i++)
            p[i][j]=p[p[i][j-1]][j-1];
    return ;
}
int find(int x){
    if(f[x]!=x) f[x]=find(f[x]);
    return f[x];
}
int lca(int x,int y,int& dist){
    dist=0;
    if(d[x]>d[y])swap(x,y);
    for(int i=large;i>=0;i--)
        if(d[y]-d[x]>=1<<i) y=p[y][i],dist+=1<<i;
    if(x==y) return x;
    for(int i=large;i>=0;i--)
        if(p[x][i]!=p[y][i]){
            x=p[x][i];
            y=p[y][i];
            dist+=1<<i+1;
        }
    dist+=2;
    return p[x][0];
}
int main(){
    freopen("ecstasy.in","r",stdin);
    freopen("ecstasy.out","w",stdout);
    memset(head,-1,sizeof(head));
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int d;
        scanf("%d",&d);
        if(d==1){
            opt[i].k=d;
            scanf("%d%d%d",&opt[i].x,&opt[i].y,&opt[i].w);
            add_edge(opt[i].x,opt[i].y,opt[i].w);
            add_edge(opt[i].y,opt[i].x,opt[i].w);
        }
        else{
            opt[i].k=d;
            scanf("%d%d",&opt[i].x,&opt[i].y);
        }
    }
    init_lca();
    for(int i=1;i<=n;i++)
        f[i]=i;
    for(int i=1;i<=m;i++){
        if(opt[i].k==1){
            f[find(opt[i].x)]=find(opt[i].y);
        }
        else{
            if(find(opt[i].x)!=find(opt[i].y)){
                printf("-1\n");
                continue;
            }
            else{
                long long dist,x=opt[i].x,y=opt[i].y,k,ans=0;
                int LCA=lca(x,y,dist);
                k=1;
                while(x!=LCA){
                    ans+=val[x]*(dist+1-k)*k;
                    k++,x=p[x][0];
                }
                k=1;
                while(y!=LCA){
                    ans+=val[y]*(dist+1-k)*k;
                    k++,y=p[y][0];
                }
                printf("%lld\n",ans);
            }
        }
    }
    return 0;
}
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+1000;
const int M=3e5;
int f[N];
struct Opt{
    int x,y,w,k;
}opt[M];
struct Edge{
    int v,c,nxt;
}edge[N<<1];
int head[N],tot=0;

int n,m,large,s=1;
long long d[N],p[N][20],val[N];
long long dis[N],ndis[N],n2dis[N];
void add_edge(int x,int y,int c){
    edge[tot].v=y;
    edge[tot].c=c;
    edge[tot].nxt=head[x];
    head[x]=tot++;
    return ;
}
void dfs(int u,int dep){
    d[u]=dep;
    for(int i=head[u];i!=-1;i=edge[i].nxt){
        int v=edge[i].v;
        if(!d[v]){
            p[v][0]=u;
            val[v]=edge[i].c;
            dis[v]=dis[u]+edge[i].c;
            ndis[v]=ndis[u]+(n-d[u])*edge[i].c;
            n2dis[v]=n2dis[u]+(n-d[u])*(n-d[u])*edge[i].c;
            dfs(v,dep+1);
        }
    }
}
void init_lca(){
    dis[s]=0,ndis[s]=0,n2dis[s]=0;
    dfs(s,1);
    p[s][0]=s;
    large=0;
    while(1<<large<=n)large++;
    large--;
    for(int j=1;j<=large;j++)
        for(int i=1;i<=n;i++)
            p[i][j]=p[p[i][j-1]][j-1];
    return ;
}
int find(int x){
    if(f[x]!=x) f[x]=find(f[x]);
    return f[x];
}
int lca(int x,int y){
    if(d[x]>d[y])swap(x,y);
    for(int i=large;i>=0;i--)
        if(d[y]-d[x]>=1<<i) y=p[y][i];
    if(x==y) return x;
    for(int i=large;i>=0;i--)
        if(p[x][i]!=p[y][i]){
            x=p[x][i];
            y=p[y][i];
        }
    return p[x][0];
}
int main(){
    memset(head,-1,sizeof(head));
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int d;
        scanf("%d",&d);
        if(d==1){
            opt[i].k=d;
            scanf("%d%d%d",&opt[i].x,&opt[i].y,&opt[i].w);
            add_edge(opt[i].x,opt[i].y,opt[i].w);
            add_edge(opt[i].y,opt[i].x,opt[i].w);
        }
        else{
            opt[i].k=d;
            scanf("%d%d",&opt[i].x,&opt[i].y);
        }
    }
    init_lca();
    for(int i=1;i<=n;i++)
        f[i]=i;
    for(int i=1;i<=m;i++){
        if(opt[i].k==1){
            f[find(opt[i].x)]=find(opt[i].y);
        }
        else{
            if(find(opt[i].x)!=find(opt[i].y)){
                printf("-1\n");
                continue;
            }
            else{
                long long dist,x=opt[i].x,y=opt[i].y;
                int LCA=lca(x,y);
                dist=d[x]+d[y]-(d[LCA]<<1);
                long long sx,sy,sx2,sy2;
                sx=ndis[x]-ndis[LCA]-(dis[x]-dis[LCA])*(n-d[x]);
                sy=ndis[y]-ndis[LCA]-(dis[y]-dis[LCA])*(n-d[y]);
                sx2=n2dis[x]-n2dis[LCA]-(dis[x]-dis[LCA])*(n-d[x])*(n-d[x])-(n-d[x])*(sx<<1);
                sy2=n2dis[y]-n2dis[LCA]-(dis[y]-dis[LCA])*(n-d[y])*(n-d[y])-(n-d[y])*(sy<<1);
                printf("%lld\n",(dist+1)*(sx+sy)-sx2-sy2);
            }
        }
    }
    return 0;
}
相关标签: 题解