HDU 4836 The Query on the Tree lca || 欧拉序列 || 动态树

HDU 4836 The Query on the Tree lca || 欧拉序列 || 动态树

大家好,又见面了,我是全栈君。

lca的做法还是非常明显的。简单粗暴,

只是不是正解。假设树是长链就会跪,直接变成O(n)、、

最后跑的也挺快,出题人还是挺阳光的。。

动态树的解法也是听别人说能ac的。预计就是放在splay上剖分一下,做法还是比較复杂的。,,

来一发lca:

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
const int maxn=20010;
int head[maxn],tol,dp[maxn],fa[maxn][20],dep[maxn],weight[maxn];
struct Edge{
    int next,to;
    Edge(int _next=0,int _to=0){
        next=_next;to=_to;
    }
}edge[10*maxn];
void addedge(int u,int v){
    edge[tol]=Edge(head[u],v);
    head[u]=tol++;
}
void bfs(int s){
    queue<int> q;
    dep[s]=0,fa[s][0]=s;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=1;i<20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
        for(int i=head[u];i!=-1;i=edge[i].next){
            int v=edge[i].to;
            if(v==fa[u][0])continue;
            fa[v][0]=u;
            dep[v]=dep[u]+1;
            q.push(v);
        }
    }
}
int LCA(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=19;i>=0;i--)if((1<<i)&(dep[x]-dep[y]))x=fa[x][i];
    if(x==y)return x;
    for(int i=19;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
void dfs(int u,int pre){
    dp[u]=weight[u];
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].to;
        if(v==pre)continue;
        dfs(v,u);
        dp[u]+=dp[v];
    }
}
int move(int x,int d){
    for(int i=19;i>=0;i--)
        if(d&(1<<i))x=fa[x][i];
    return x;
}
int main()
{
     int T;
     cin>>T;
     for(int t=1;t<=T;t++){
         int n;
         scanf("%d",&n);
         memset(head,-1,sizeof(head));tol=0;
         for(int i=1;i<n;i++){
             int x,y;
             scanf("%d%d",&x,&y);
             addedge(x,y);
             addedge(y,x);
         }
         bfs(1);
         for(int i=1;i<=n;i++)scanf("%d",&weight[i]);
         dfs(1,-1);
         printf("Case #%d:\n",t);
         int Q;
         scanf("%d",&Q);
         int root=1;
         while(Q--){
             char op[10];
             int x,y;
             scanf("%s",op);
             if(op[0]=='R'){
                 scanf("%d",&x);
                 root=x;
             }
             else if(op[0]=='C'){
                 scanf("%d%d",&x,&y);
                 int dd=x;
                 while(1){
                     dp[dd]+=y-weight[x];
                     if(dd==1)break;
                     dd=fa[dd][0];
                 }
weight[x] = y;
             }
             else {
                 scanf("%d",&x);
                 if(x==root)printf("%d\n",dp[1]);
                 else {
                     int lca=LCA(x,root);
                     if(lca==x){
                         int p=move(root,dep[root]-dep[x]-1);
                         //cout<<"han "<<x<<" "<<root<<" "<<dep[root]-dep[x]-1<<endl;cout<<"p="<<p<<endl;
                         printf("%d\n",dp[1]-dp[p]);
                     }
                     else printf("%d\n",dp[x]);
                 }
             }
         }
     }
     return 0;
}

正解应该是树状数组维护欧拉序列,,

bit的神牛教的。,

详见:点击打开链接

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116158.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • linux的vim显示行号(vim添加行号)

    打开vim的配置文件/etc/vim/vimrcsudovim/etc/vim/vimrc然后找到#setnumber,把注释取消就行了如果没有,就自己加一行转载于:https://www.cnblogs.com/zdj8023/p/10837480.html…

  • tar 打包压缩命令

    tar 打包压缩命令tar命令用于文件的打包或压缩,是最为常用的打包压缩命令,其语法格式如下:tar[选项]文件名.tar.gz源文件tar-cvfzxxx.tar.gzsource_file(tar-cvfz包名.tar.gz源文件)#以tar.gz方式打包并gz方式压缩tar-xvfzxxx.tar.gz-Cpath(tar-xvfzxxx.tar.gz-C目标路径)#解压缩包注意:使用tar命令,打包仅仅是打包xxx.tar,打包

  • PLsql 永久注册码「建议收藏」

    PLsql 永久注册码「建议收藏」 注册码:ProductCode:4t46t6vydkvsxekkvf3fjnpzy5wbuhphqzserialNumber:601769password:xs374ca  原文链接:https://blog.csdn.net/sinat_33142609/article/details/72540025

  • 如何在vue组件中引入外部的css和js文件[通俗易懂]

    如何在vue组件中引入外部的css和js文件[通俗易懂]在使用vue框架开发时,我们都知道一个组件中可以同时写HTML、css、js代码,只需三个标签而已,如下:但是要真把所有的代码都写入一个组件文件当中,那么代码量是非常大的,极不便于修改和维护,这时就需要把css样式和js代码写到其他文件下,再引入组件当中。具体方法如下:在组件中引入css文件:<style>@importurl(css文件路径)</style>在组件中引入js文件:首先需要将我们…

  • 模电——基本运算放大器原理[通俗易懂]

    模电——基本运算放大器原理[通俗易懂]★运算放大器电路图标:Vp:同相输入端Vn:反向输入端Vo:输出端1.同相输入端与反向输入端的意义。 同相位 Vp Vn Vo 上升 接地或稳定的电平 上升 下降 接地或稳定的电平 下降 反相位 Vp Vn Vo 上升 接地或稳定的电平 下降 .

  • 数独口诀_数独技巧xwing推导过程

    数独口诀_数独技巧xwing推导过程数独是一种传统益智游戏,你需要把一个 9×9 的数独补充完整,使得图中每行、每列、每个 3×3 的九宫格内数字 1∼9 均恰好出现一次。请编写一个程序填写数独。输入格式输入包含多组测试用例。每个测试用例占一行,包含 81 个字符,代表数独的 81 个格内数据(顺序总体由上到下,同行由左到右)。每个字符都是一个数字(1−9)或一个 .(表示尚未填充)。您可以假设输入中的每个谜题都只有一个解决方案。文件结尾处为包含单词 end 的单行,表示输入结束。输出格式每个测试用例,输出一行数据,代表填充

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号