传送门:Problem 2763

https://www.cnblogs.com/violet-acmer/p/9686774.html

题意:

  一对夫妇居住在xx村庄,小屋之间有双向可达的道路,不会出现环,即所构成的图是个树,从ai小屋到bi小屋需要花费wi时间,一开始,女主角在s小屋,有两个询问,

  ①0 u : 她又个孩子在u屋,需要妈妈接她回家,输出从s到u所需的最短时间。

  ②1 x val : 由于种种原因,第x条道路的行走时间由之前的w[x]变为了val。

题解:

  (1)RMQ+BIT

    因为树中连接两点的路径是唯一的,如果我们对顶点进行合理排列的话,能否像链状时那样,进行类似的处理呢?

    考虑利用RMQ计算LCA时所用的,按DFS访问的顺序排列顶点序列。

    这样,u和v之间的路径,就是在序列中u 和 v 之间的所有边减去往返重复的部分得到的结果。

    于是,只要令边的权重沿叶子方向为正,沿根方向为负,那么往返重复的部分就自然抵消了,于是有

        (u,v之间的花费的时间)=(从LCA(u,v)到u的花费的时间和)+(从LCA(u,v)到v的花费的时间和);

    同链状情况一样,利用BIT的话,计算权重和更新边权都可以在O(logn)时间内办到,而LCA也能够在O(longn)时间内求得。

  (2)树链剖分

AC代码:

 #include<iostream>
 #include<cstdio>
 #include<cmath>
 #include<cstring>
 #include<vector>
 using namespace std;
 #define pb push_back
 #define mem(a,b) (memset(a,b,sizeof a))
 #define lowbit(x) (x&(-x))
 ;

 int n,q,s;
 int w[maxn];//存储第 i 条边的权值
 struct Node
 {
     int to;
     int w;
     int id;
     Node(int to,int w,int id):to(to),w(w),id(id){}
 };
 vector<Node >G[maxn];
 void addEdge(int u,int v,int cost,int id)
 {
     G[u].pb(Node(v,cost,id));
     G[v].pb(Node(u,cost,id));
 }
 *maxn];//欧拉序列
 *maxn];//深度序列
 int id[maxn];//id[i] : 记录节点 i 在欧拉序列中第一次出现的位置
 *maxn];//边的下标,i*2 : 叶子方向 i*2+1 : 根方向
 int total;//记录欧拉序列的下标总个数,其实最终的 total = 2*n
 //================BIT==================
 *maxn];//树状数组
 void Add(int x,int val)
 {
     *maxn)
     {
         bit[x] += val;
         x += lowbit(x);
     }
 }
 int Sum(int x)
 {
     ;
     )
     {
         sum += bit[x];
         x -= lowbit(x);
     }
     return sum;
 }
 //=====================================
 //==================RMQ================
 struct RMQ
 {
     ][*maxn];
     void Init(){
         ;i < *maxn;++i)
             dp[][i]=i;
     }
     void ST()
     {
         );
         ;i <= k;++i)
             ;j <= (total-(<<i));++j)
                 ][j]] > depth[dp[i-][j+(<<(i-))]])//dp[i][j] : 记录的是下标
                     dp[i][j]=dp[i-][j+(<<(i-))];
                 else
                     dp[i][j]=dp[i-][j];
     }
     int Lca(int u,int v)
     {
         if(u > v)
             swap(u,v);
         )/log();
         <<k)+]])
             <<k)+]];
         return vs[dp[k][u]];//返回 u,v 的lca
     }
 }_rmq;
 //=====================================
 void Dfs(int u,int f,int d)
 {
     vs[total]=u;
     depth[total]=d;
     id[u]=total++;
     ;i < G[u].size();++i)
     {
         Node &e=G[u][i];
         if(e.to != f)
         {
             Add(total,e.w);//叶子方向,+e.w
             es[*e.id]=total;//记录朝向叶子方向的边
             Dfs(e.to,u,d+);
             vs[total]=u;
             depth[total++]=d;
             Add(total,-e.w);//根方向, -e.w
             es[*e.id+]=total;//记录朝向根方向的边
         }
     }
 }
 void Init()
 {
     _rmq.Init();
     total=;
     mem(bit,);
     ;i < maxn;++i)
         G[i].clear();
 }
 int main()
 {
     while(~scanf("%d%d%d",&n,&q,&s))
     {
         Init();
         ;i < n;++i)
         {
             int u,v;
             scanf("%d%d%d",&u,&v,w+i);
             addEdge(u,v,w[i],i);
         }
         Dfs(,-,);
         _rmq.ST();
         ;i <= q;++i)
         {
             int type;
             scanf("%d",&type);
             )
             {
                 int u;
                 scanf("%d",&u);
                 int lca=_rmq.Lca(id[u],id[s]);
                 printf(*Sum(id[lca]));
                 s=u;
             }
             else
             {
                 int x,val;
                 scanf("%d%d",&x,&val);
                 Add(es[x*],val-w[x]);//w[x] 变为 val,需要在原基础上加上 val-w[x]
                 Add(es[x*+],w[x]-val);//朝向根方向的加负值
                 w[x]=val;
             }
         }
     }
     ;
 }

RMQ+BIT

  

最新文章

  1. keras安装
  2. linux 学习 day1
  3. GO语言练习:组合的用法
  4. Python数据
  5. Hibernate的关联映射——单向N-1关联
  6. nginx看端口使用情况
  7. Ubuntu12.04 Eclipse 提示框背景色修改
  8. Intellij IDEA中文乱码解决
  9. 清理我的 Mac
  10. Java Web项目(Extjs)报错三
  11. 10倍速!一招儿解决因googleapis被墙导致的许多国外网站访问速度慢的问题
  12. mac连接windows远程桌面及文件复制
  13. 在macOS下使用MAXPP搭建本地开发服务器简易流程
  14. Android Spinner 绑定键值对
  15. docker部署rabbitMQ
  16. MySQL命令行查询乱码解决办法
  17. 25. LiveBos调用class实例
  18. php中ip转int 并存储在mysql数据库
  19. CALayer的additive属性解析
  20. (转)MapReduce Design Patterns(chapter 1)(一)

热门文章

  1. http 概念
  2. 个人博客week7
  3. 《Linux内核分析》实践2
  4. 《Linux内核分析》课程第八周学习总结
  5. 《linux内核设计与分析》内核模块编程
  6. 生命游戏&amp;一维细胞自动机 笔记
  7. 第一次Sprint
  8. java注解的简单介绍
  9. 09-java学习-数组-冒泡排序-选择排序-数组工具类编写-查找-扩容
  10. MyBatis自动生成Java/C#的Bean(Entity)的等价MYSQL实现函数