CodeForces 191C 树链剖分 第4遍「建议收藏」

CodeForces 191C 树链剖分 第4遍

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

非常无奈,模板重新无奈的打错了。。

只是,非常快便找到了。。

题意:给一些边,有一些操作,每次操作,都要在这些边上加上1,求每一个边的边权。。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define lson id << 1
#define rson id << 1|1
const int M = 100008;
int top[M],siz[M],son[M],father[M],ti[M],dep[M];
int e[M][2],idx,tp;
struct {
    int head;
}H[M];
struct{
    int v,next;
}E[M*2];
void init(){
    memset(H,-1,sizeof(H));
    memset(E,-1,sizeof(E));
    tp = 0,idx = 0;
}
void add(int u,int v){
    E[tp].v =v;
    E[tp].next = H[u].head;
    H[u].head = tp++;
}
void dfs_1(int u,int fa){
    son[u] = 0;siz[u] = 1;father[u] = fa;dep[u] = dep[fa] + 1;
    for(int i=H[u].head;i!=-1;i=E[i].next){
        int v = E[i].v;
        if(v == fa)continue;
        dfs_1(v,u);
        siz[u] += siz[v];
        if(siz[v] > siz[son[u]])son[u] = v;
    }
}
void dfs_2(int u,int fa){
    ti[u] = idx++;
    top[u] = fa;
    if(son[u])dfs_2(son[u],fa);
    for(int i=H[u].head;i!=-1;i=E[i].next){
        int v = E[i].v;
        if(v == father[u]|| v == son[u])continue;
        dfs_2(v,v);
    }
}
struct M_tree{
    int mark,l,r;
    int mid(){
        return (l+r) /2;
    }
}node[M*4];
void  build_tree(int id,int l,int r){
    node[id].l = l;node[id].r = r;node[id].mark = 0;

    if(l == r)return;
    int mid = node[id].mid();
    build_tree(lson,l,mid);
    build_tree(rson,mid+1,r);
}
void push_down(int id){
    if(node[id].l == node[id].r)return;
    if(node[id].mark){
        node[lson].mark += node[id].mark ;
        node[rson].mark += node[id].mark ;
        node[id].mark = 0;
    }
}

void nede(int id,int l,int r){

    if(node[id].l == l&&node[id].r == r){

        node[id].mark += 1;
        return;
    }
    push_down(id);
    int mid = node[id].mid();
    if(r <=mid)nede(lson,l,r);
    else if(l > mid)nede(rson,l,r);
    else{
        nede(lson,l,mid);
        nede(rson,mid+1,r);
    }
}
int ans = 0;
int query(int id,int r){

    if( node[id].l == r&&node[id].r == r)return node[id].mark;
    push_down(id);
    int mid= node[id].mid();
    if(r <=mid)return query(lson,r);
    else return query(rson,r);
}
void negat(int u,int v){
    int f1 = top[u];
    int f2 = top[v];

    while(f1 != f2){
        if(dep[f1] < dep[f2]){
            swap(f1,f2);
            swap(u,v);
        }//cout << ti[f1] << "<---->" << ti[u]<<endl;
        nede(1,ti[f1],ti[u]);
        u = father[f1];f1 = top[u];
    }
    if(u == v)return;
    if(dep[u] > dep[v])swap(u,v);
    nede(1,ti[son[u]],ti[v]);
}
int main()
{
    int u,v,n,m;
    while(~scanf("%d",&n)){
            init();
       for(int i=0;i<n-1;i++){
        scanf("%d%d",&e[i][0],&e[i][1]);
        add(e[i][0],e[i][1]);
        add(e[i][1],e[i][0]);

       }
       dfs_1(1,1);
       dfs_2(1,1);
       build_tree(1,0,idx-1);
//cout <<idx<<endl;
       scanf("%d",&m);
       while(m--){
            scanf("%d%d",&u,&v);

            negat(u,v);
       }
       for(int i=0;i<n-1;i++)
       {
           if(dep[e[i][0]] > dep[e[i][1]]){
            swap(e[i][0],e[i][1]);
           }
       }
       for(int i=0;i<n-1;i++){
            printf("%d",query(1,ti[e[i][1]]));
            if(i!=n-2)printf(" ");
       }
       printf("\n");
    }
}

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

发布者:全栈程序员-站长,转载请注明出处:https://javaforall.net/116097.html原文链接:https://javaforall.net

(0)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • file.encoding的简单学习 java

    file.encoding的简单学习 java

    2021年8月28日
    54
  • mysql命令窗口_HLOOKUP函数

    mysql命令窗口_HLOOKUP函数窗口:记录集合窗口函数:在满足某些条件的记录集合上执行的特殊函数,对于每条记录都要在此窗口内执行函数。有的函数随着记录的不同,窗口大小都是固定的,称为静态窗口;有的函数则相反,不同的记录对应着不同的窗口,称为滑动窗口。1.窗口函数和普通聚合函数的区别:①聚合函数是将多条记录聚合为一条;窗口函数是每条记录都会执行,有几条记录执行完还是几条。②聚合函数也可以用于窗口函数。2.窗口函数的基…

    2022年10月4日
    4
  • Web 3D机房,智能数字机房HTML5 WebGL(ThreeJS)匠心打造「建议收藏」

    Web 3D机房,智能数字机房HTML5 WebGL(ThreeJS)匠心打造「建议收藏」在H5使用3D技术门槛比较低了,它的基础是WebGL(ThreeJS),一个OpenGL的浏览器子集,支持大部分主要3D功能接口。目前主流的浏览器都有较好的支持,IE需要11。最近web3D机房研发告一段落,有时间整理这段时间的一些成果。主要涉及使用H5、js、WebGL技术。机房3D效果图机房线缆和走线架线缆的连接走向和连接关系是管理员关注的焦点。机架中…

    2022年5月5日
    159
  • U872在企业平台中做自定义报表显示空白的格子

    U872在企业平台中做自定义报表显示空白的格子问题:在企业平台中做自定义报表时,调试的时候通过,但是打开的时候却有记录却没有显示出数据,出现空白的格子。解决办法:在SQL查询分析器中,我们看到了源码,发现定义别名的时候后面使用了多余的空格,可能是空格引出了问题,把空格删除后,运行正常。 

    2022年9月27日
    3
  • python进入文件目录 命令_python创建目录

    python进入文件目录 命令_python创建目录python进入到指定目录下的方法:Python可以使用os.chdir()方法转到指定目录。os.chdir()方法用于改变当前工作目录到指定的路径。chdir()方法语法格式如下:os.chdir(path)参数path–要切换到的新路径。实例以下实例演示了chdir()方法的使用:#!/usr/bin/python#-*-coding:UTF-8-*-importos,…

    2022年8月31日
    3
  • 使用批处理命令向win server AD域中批量添加用户实现

    使用批处理命令向win server AD域中批量添加用户实现因为要用个批处理命令在WindowsServer里面批量添加域用户,所以需要使用批处理命令。我这篇是纯新手教程,在百度上搜了一些批处理命令感觉属于进阶教程,研究了两天才完成我要完成的目标。下面从头说一下:批处理bat文档建立。直接新建一个TXT文档然后把后缀名改成.bat就可以了,就是一个bat文档,双击可以运行。注意:bat文件在哪,他的运行路径就在哪。添加成功的用户

    2022年5月13日
    46

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

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