【日常学习】【倍增LCA】codevs2370 小机房的树题解

小灰灰 2022-08-08 15:52 143阅读 0赞

题目描述 Description

小机房有棵焕狗种的树，树上有N个节点，节点标号为0到N-1，有两只虫子名叫飘狗和大吉狗，分居在两个不同的节点上。有一天，他们想爬到一个节点上去搞基，但是作为两只虫子，他们不想花费太多精力。已知从某个节点爬到其父亲节点要花费 c 的能量（从父亲节点爬到此节点也相同），他们想找出一条花费精力最短的路，以使得搞基的时候精力旺盛，他们找到你要你设计一个程序来找到这条路，要求你告诉他们最少需要花费多少精力

输入描述 Input Description

第一行一个n，接下来n-1行每一行有三个整数u，v, c 。表示节点 u 爬到节点 v 需要花费 c 的精力。
    第n+1行有一个整数m表示有m次询问。接下来m行每一行有两个整数 u ，v 表示两只虫子所在的节点

输出描述 Output Description

一共有m行，每一行一个整数，表示对于该次询问所得出的最短距离。

样例输入 Sample Input

1 0 1

2 0 1

1 0

2 0

1 2

样例输出 Sample Output

数据范围及提示 Data Size & Hint

1<=n<=50000， 1<=m<=75000， 0<=c<=1000

显然这是裸的LCA 我们用倍增来写 因为tanjan不会

但我们一定要注意：邻接表要开两倍！！！邻接表要开两倍！！！邻接表要开两倍！！！重要的事情说三遍！因为你WA了三遍！！！

codevs2370 小机房的树 LCA最近公共祖先 目前现状：A一半W一半 大数据W 静态查代码 
    //copyright by ametake
    #include
       
        
    #include
        
         
    #include
         
          
    using namespace std;
    
    const int maxn=50000+10;
    int p[maxn][20],cost[maxn][20];//cost表示从节点i向上蹦2^j至某一节点t的路程中花费的精力和
    int father[maxn];
    int depth[maxn];
    int power[20];
    int et=0,t[maxn],val[maxn],head[maxn],next[maxn];//边的编号，去路，权值，以同一节点开始的第一条边的编号，这条边连接的下一条编的编号 
    int n;
    
    void add(int from,int to,int v)
    {
        et++;
        t[et]=to;
        val[et]=v;
        next[et]=head[from];
        head[from]=et;
    }
    
    void makepower()
    {
        power[0]=1;
        power[1]=2;
        int cnt=1;
        for (int i=2;i<20;i++)
        {
            power[cnt+1]=power[cnt]*2;
            cnt++;
        }
    }
    
    void dfs(int now)
    {
        int i=head[now];
        while (i!=0)
        {
            if (depth[t[i]])
            {
            	i=next[i];
            	continue;
    		}
            depth[t[i]]=depth[now]+1;
            father[t[i]]=now;//notice
            cost[t[i]][0]=val[i];
            dfs(t[i]);
        }
    }
    
    void doit()
    {
        for (int i=1;i<=n;i++)
        {
            p[i][0]=father[i];
        } 
        for (int j=1;j<20;j++)
        {
            for (int i=1;i<=n;i++)
            {
                p[i][j]=p[p[i][j-1]][j-1];
                cost[i][j]=cost[p[i][j-1]][j-1]+cost[i][j-1];
            }
        }
    }
    
    int lca(int u,int v)
    {
        int ans=0;
        if (depth[u]
          
           =0;j--)
        {
            if (dt==0) break;
            if (power[j]<=dt)//<= not <
            {
                dt-=power[j];
                ans+=cost[u][j];
                u=p[u][j];
            }
        }
        for (int j=19;j>=0;j--)
        {
            if (p[u][j]!=p[v][j])
            {
                ans+=cost[u][j];
                ans+=cost[v][j];
                v=p[v][j];
                u=p[u][j];
            }
        }
        if (u!=v)
        {
        	ans=ans+cost[u][0];
            ans=ans+cost[v][0];
        }
        return ans;
    }
    
    
    int main()
    {
        freopen("1.txt","r",stdin);
        scanf("%d",&n);
        int u,v,c;
        memset(head,0,sizeof(head));
        for (int i=1;i

详细的注释，可以看洛谷某道题目的代码 比赛还没有结束 但我估计这里的代码不会被搜到吧？

裸的LCA 只不过要把加改为异或而已

//B
    //所谓树上倍增= =LCA没过 这个要能过就是奇迹
    
    
    
    //codevs2370 小机房的树 LCA最近公共祖先 目前现状：A一半W一半 大数据W 静态查代码 
    //copyright by ametake
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    
    const int maxn=200000+20;
    int p[maxn][22],cost[maxn][22];//cost表示从节点i向上蹦2^j至某一节点t的路程中花费的精力和
    int father[maxn];//某个点的父亲 
    int depth[maxn];//某个点的层次 
    int power[22];
    int et=0,t[maxn],val[maxn],head[maxn],next[maxn];//边的编号，去路，权值，以同一节点开始的第一条边的编号，这条边连接的下一条编的编号 
    int n;
    
    void add(int from,int to,int v)
    {
        et++;
        t[et]=to;
        val[et]=v;
        next[et]=head[from];
        head[from]=et;
    }
    /*
    void makepower()
    {
        power[0]=1;
        power[1]=2;
        int cnt=1;
        for (int i=2;i<20;i++)
        {
            power[cnt+1]=power[cnt]*2;
            cnt++;
        }
    }
    */
    void dfs(int now)
    {
        int i=head[now];//开始时，i是起点为1的第一条边 now==1 
        while (i!=0)//
        {
            if (depth[t[i]])//如果这条边的终点有层次，也就是访问过，是原节点的父亲 
            {
            	i=next[i];//更新i 跳到1为起点的下一条边 
            	continue;//不再进行后面的 直接进入下一次循环 
    		}
            depth[t[i]]=depth[now]+1;//i这条边的终点的层次是now（起点）层次+1 
            father[t[i]]=now;//notice 终点的父亲是起点 
            cost[t[i]][0]=val[i];//终点向上一位的总异或值是这条边的边权   !!!务必注意输入两个相同的点输出0 
            dfs(t[i]);//搜索以终点为起点的所有边 即终点的儿子们 
        }
    }
    
    void doit()
    {
        for (int i=1;i<=n;i++)
        {
            p[i][0]=father[i];//每个点上面一个点是他的父亲 
        } 
        for (int j=1;j<20;j++)
        {
            for (int i=1;i<=n;i++)
            {
                p[i][j]=p[p[i][j-1]][j-1];//求祖先 
                cost[i][j]=((cost[p[i][j-1]][j-1])^(cost[i][j-1]));//从i向上数2^j个点 如果j是1 i=1,ij=3 这条路上的异或值  
            }
        }
    }
    
    int lca(int u,int v)
    {
        int ans=0;
        if (u==v) return 0; 
        if (depth[u]<depth[v]) swap(u,v);//u是深度深的那个 u是儿子 先蹦 
        int dt=depth[u]-depth[v];
        /*for (int j=19;j>=0;j--)//可以尝试每次更新dt 做完后跳到同一层 
        {
            if (dt==0) break;
            if (power[j]<=dt)//<= not <
            {
                dt-=power[j];
                ans=(cost[u][j]^ans);
                u=p[u][j];
            }
        }*/
        for (int j=19;j>=0;j--)//可以尝试每次更新dt 做完后跳到同一层 
        {
            if (dt==0) break;
            if ((1<<j)<=dt)//<= not <
            {
                dt-=(1<<j);
                ans=(cost[u][j]^ans);
                u=p[u][j];
            }
        }
        if (u==v) return ans;
        for (int j=19;j>=0;j--)//做完这一步 如果不是父子关系两个有共同的父亲 
        {
            if (p[u][j]!=p[v][j])
            {
                ans=(cost[u][j]^ans);
                ans=(cost[v][j]^ans);
                v=p[v][j];
                u=p[u][j];
            }
        }
        if (u!=v)
        {
        	ans=(ans^cost[u][0]);
            ans=(ans^cost[v][0]);
        }
        return ans;
    }
    
    
    int main()
    {
        freopen("1.txt","r",stdin);
        scanf("%d",&n);
        int u,v,c;
        memset(head,0,sizeof(head));
        for (int i=1;i<n;i++)
        {
            scanf("%d%d%d",&u,&v,&c);
            add(u,v,c);
            add(v,u,c);
        }
        memset(father,0,sizeof(father));
        memset(depth,0,sizeof(depth)); 
        //makepower();//作用：求出2的幂次方 
        father[1]=1;//点1的父亲和层次都是1 也就是说1是根 
        depth[1]=1;
        dfs(1);//从1为起点的边开始搜索 经检验无误XD 
        doit();//求值 
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
        {
            scanf("%d%d",&u,&v);
            printf("%d\n",lca(u,v));
        }
        while(1);
        return 0;
    }
    
    /*
    *B的处理思路
    *首先读入边 无向图邻接表存
    *由于要求的是路径上边权的异或，还是和机房一样，还是先跑一边LCA然后求cost 区别是不是求和是异或 
    *思路参考下面 
    */
    
    /*
    *首先读入边 邻接表存储
    *然后DFS一次，求层次和father
    *然后预处理出来p和cost
    *对每个数据进行计算 
    */

需要注意的是 这个程序原本计算二的幂次方存储 后来发现位运算是个好东西

今天忙了一天比赛以及未来规划 也够累了 想去刷几个题目 还要刷作业 所以要加油了

安排了下明年暑假 这么早安排没啥实用性 但也算吃了颗定心丸 然后发现暑假时间好紧挤不出来 所以现在要更加努力努力好好学代码好好学文化课打好基础 这样暑假学软件硬件和预科就要轻松些了

今天我有三个梦想：我要环游世界，我要做一流的极客和技术宅，我要做一个有自己的思想、有文化、有修养的人。

为了实现我的梦想，我要在高三一年努力打好基础 创造必要条件 为自己的梦想提供基础保障

为了实现我的梦想，我要在高三专注拼搏，专注只做这一件事，为自己谋求最优质的资源和环境

为了实现我的梦想，高三一结束，我即踏上征程，一天也等不及

希望一年后的今天 当我再看到这篇文章 梦想已经在路上

希望十年后的今天 当我再看到这篇文章 我能露出欣慰的微笑而不是无奈或悔恨的眼泪 因为我有勇气 我能做到 我会努力 我知道我年轻 我知道我的人生只有这一次 精神快乐比物质富足更重要 我知道我现在追求的是什么 我也会一直学习 不断充实和修正我的追求

写这些斗志昂扬的话，那么就努力去做吧。

——我欲穿花寻路，直入白云深处，浩气展虹霓。