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)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • 基于粒子群优化算法的函数寻优算法研究_matlab粒子群优化算法

    基于粒子群优化算法的函数寻优算法研究_matlab粒子群优化算法一、理论基础粒子群算法(particleswarmoptimization,PSO)是计算智能领域一种群体智能的优化算法。该算法最早由Kennedy和Eberhart在1995年提出的。PSO算法源于对鸟类捕食行为的研究,鸟类捕食时,找到食物最简单有效的策略就是搜寻当前距离食物最近的鸟的周围区域。PSO算法就是从这种生物种群行为特征中得到启发并用于求解优化问题的,算法中每个粒子都代表问题的一个潜在解,每个粒子对应一个由适应度函数决定的适应度值。粒子的速度决定了粒子移动的方向和距离,速度随自身及其他粒子

    2022年10月11日
    2
  • Oracle 更改表名称的几种方式

    Oracle 更改表名称的几种方式1:使用命令直接修改(推荐)ALTERTABLEold_table_nameRENAMETOnew_table_name;(大写为系统命令)2:使用rename修改 SQL>selecttnamefromtab;TNAME——————————TESTSQL>renametesttotemp;T

    2022年5月16日
    58
  • 度量学习系列(2):有监督度量学习

    度量学习系列(2):有监督度量学习有监督度量学习算法利用输入点xxx与目标标签yyy作为来学习一个距离矩阵,这个距离矩阵拉近同类别的点(分类问题)或者目标值邻近的点(回归问题)的距离,并使不同类别或目标值相差大的点的互相远离。1.通用API有监督的度量学习算法实质上利用了与scikit-learn相同的应用程序接口(API)。1.1输入数据为了训练一个模型,我们需要两个array-like对象:XXX与yyy。XX…

    2022年6月23日
    27
  • 我为什么离开神州泰岳

    我为什么离开神州泰岳

    2021年11月13日
    62
  • 怎么将python代码编译_python怎么编译运行

    怎么将python代码编译_python怎么编译运行有时为了一些机密,不方便公开python源码,所以需要以编译方式进行部署。这里主要介绍以.pyc的方式。1、生成单个文件:(1)python-mxx.py(2)在python编译器中进行:importpy_compilepy_compile.compile(‘路径’)2、批量生成文件:importcompileallcompileall.compile_dir(r’/pat………

    2025年7月20日
    3
  • 常见的黑盒测试方法有哪些_黑盒测试方法10种

    常见的黑盒测试方法有哪些_黑盒测试方法10种常见的黑盒测试方法

    2022年10月3日
    2

发表回复

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

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