【国家集训队2012】tree(伍一鸣)

时间:2022-01-31 05:35:46

Description
一棵n个点的树,每个点的初始权值为1。对于这棵树有q个操作,每个操作为以下四种操作之一: 
+ u v c:将u到v的路径上的点的权值都加上自然数c; 
- u1 v1 u2 v2:将树中原有的边(u1,v1)删除,加入一条新边(u2,v2),保证操作完之后仍然是一棵树; 
* u v c:将u到v的路径上的点的权值都乘上自然数c; 
/ u v:询问u到v的路径上的点的权值和,求出答案对于51061的余数。

Input
第一行两个整数n,q 
接下来n-1行每行两个正整数u,v,描述这棵树 
接下来q行,每行描述一个操作

Output
对于每个/对应的答案输出一行

Sample Input
3 2 
1 2 
2 3 
* 1 3 4 
/ 1 1

Sample Output
4

Hint
数据规模: 
10%的数据保证,1<=n,q<=2000 
另外15%的数据保证,1<=n,q<=5 * 10^4,没有-操作,并且初始树为一条链 
另外35%的数据保证,1<=n,q<=5 * 10^4,没有-操作 
100%的数据保证,1<=n,q<=10^5,0<=c<=10^4

正解:link-cut tree。

毒瘤数据结构题,调了我一下午。。主要是加和乘的lazy标记,下放时如果是乘,那么加的那个标记也要同乘,并且要先下放乘的标记,再下放加的标记。

 //It is made by wfj_2048~
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define inf (1<<30)
#define r64 (51061)
#define N (100010)
#define il inline
#define RG register
#define uint unsigned int
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) using namespace std; uint ch[N][],fa[N],size[N],lazy[N],st[N],rev1[N],rev2[N],val[N],sum[N],n,q;
char s[]; il uint gi(){
RG uint x=,q=; RG char ch=getchar(); while ((ch<'' || ch>'') && ch!='-') ch=getchar();
if (ch=='-') q=-,ch=getchar(); while (ch>='' && ch<='') x=x*+ch-,ch=getchar(); return q*x;
} il void pushdown(RG uint x){
RG uint &l=ch[x][],&r=ch[x][];
if (lazy[x]) lazy[x]=,lazy[l]^=,lazy[r]^=,swap(l,r);
if (rev2[x]!=){
(val[l]*=rev2[x])%=r64,(val[r]*=rev2[x])%=r64;
(sum[l]*=rev2[x])%=r64,(sum[r]*=rev2[x])%=r64;
(rev1[l]*=rev2[x])%=r64,(rev1[r]*=rev2[x])%=r64;
(rev2[l]*=rev2[x])%=r64,(rev2[r]*=rev2[x])%=r64,rev2[x]=;
}
if (rev1[x]){
(val[l]+=rev1[x])%=r64,(val[r]+=rev1[x])%=r64;
(sum[l]+=rev1[x]*(size[l]%r64))%=r64,(sum[r]+=rev1[x]*(size[r]%r64))%=r64;
(rev1[l]+=rev1[x])%=r64,(rev1[r]+=rev1[x])%=r64,rev1[x]=;
}
return;
} il void pushup(RG uint x){
sum[x]=(sum[ch[x][]]+sum[ch[x][]]+val[x])%r64;
size[x]=size[ch[x][]]+size[ch[x][]]+; return;
} il uint isroot(RG uint x){ return ch[fa[x]][]!=x && ch[fa[x]][]!=x; } il void rotate(RG uint x){
RG uint y=fa[x],z=fa[y],k=ch[y][]==x; if (!isroot(y)) ch[z][ch[z][]==y]=x; fa[x]=z;
ch[y][k^]=ch[x][k],fa[ch[x][k]]=y,ch[x][k]=y,fa[y]=x,pushup(y),pushup(x); return;
} il void splay(RG uint x){
RG uint top=; st[++top]=x;
for (RG uint i=x;!isroot(i);i=fa[i]) st[++top]=fa[i];
while (top) pushdown(st[top--]);
while (!isroot(x)){
RG uint y=fa[x],z=fa[y];
if (!isroot(y)){ if ((ch[z][]==y)^(ch[y][]==x)) rotate(x); else rotate(y); }
rotate(x);
}
return;
} il void access(RG uint x){ RG uint t=; while (x) splay(x),ch[x][]=t,pushup(x),t=x,x=fa[x]; return; } il void split(RG uint x){ access(x),splay(x); return; } il void makeroot(RG uint x){ split(x),lazy[x]^=; return; } il void link(RG uint x,RG uint y){ makeroot(x),fa[x]=y; return; } il void cut(RG uint x,RG uint y){ makeroot(x),split(y),ch[y][]=fa[x]=,pushup(y); return; } il void add(RG uint x,RG uint y,RG uint v){
makeroot(x),split(y),(rev1[y]+=v)%=r64,(val[y]+=v)%=r64,(sum[y]+=v*(size[y]%r64))%=r64; return;
} il void times(RG uint x,RG uint y,RG uint v){
makeroot(x),split(y),(rev1[y]*=v)%=r64,(rev2[y]*=v)%=r64,(val[y]*=v)%=r64,(sum[y]*=v)%=r64; return;
}
il uint query(RG uint x,RG uint y){ makeroot(x),split(y); return sum[y]; } il void work(){
n=gi(),q=gi(); RG uint u,v,c; for (RG uint i=;i<=n;++i) sum[i]=val[i]=rev2[i]=size[i]=;
for (RG uint i=;i<n;++i) u=gi(),v=gi(),link(u,v);
for (RG uint i=;i<=q;++i){
scanf("%s",s); if (s[]=='+') u=gi(),v=gi(),c=gi(),add(u,v,c);
if (s[]=='-') u=gi(),v=gi(),cut(u,v),u=gi(),v=gi(),link(u,v);
if (s[]=='*') u=gi(),v=gi(),c=gi(),times(u,v,c);
if (s[]=='/'){ u=gi(),v=gi(); printf("%u\n",query(u,v)); }
}
return;
} int main(){
File("tree");
work();
return ;
}

【国家集训队2012】tree(伍一鸣)的更多相关文章

  1. 数据结构(动态树):&lbrack;国家集训队2012&rsqb;tree&lpar;伍一鸣&rpar;

    [问题描述] 一棵n个点的树,每个点的初始权值为1.对于这棵树有q个操作,每个操作为以下四种操作之一: + u v c:将u到v的路径上的点的权值都加上自然数c: - u1 v1 u2 v2:将树中原 ...

  2. &lbrack;COGS 1799&rsqb;&lbrack;国家集训队2012&rsqb;tree&lpar;伍一鸣&rpar;

    Description 一棵n个点的树,每个点的初始权值为1.对于这棵树有q个操作,每个操作为以下四种操作之一: + u v c:将u到v的路径上的点的权值都加上自然数c: - u1 v1 u2 v2 ...

  3. cogs1799 &lbrack;国家集训队2012&rsqb;tree&lpar;伍一鸣&rpar;

    LCT裸题 注意打标记之间的影响就是了 这个膜数不会爆unsigned int #include<cstdio> #include<cstdlib> #include<a ...

  4. &lbrack;国家集训队2012&rsqb;tree&lpar;陈立杰&rpar;

    [国家集训队2012]tree(陈立杰) 题目 给你一个无向带权连通图,每条边是黑色或白色.让你求一棵最小权的恰好有need条白色边的生成树.题目保证有解. INPUT 第一行V,E,need分别表示 ...

  5. &lbrack;国家集训队2012&rsqb;tree&lpar;陈立杰&rpar; 题解(二分&plus;最小生成树)

    tree 时间限制: 3 Sec  内存限制: 512 MB 题目描述 给你一个无向带权连通图,每条边是黑色或白色.让你求一棵最小权的恰好有need条白色边的生成树. 题目保证有解. 输入 第一行V, ...

  6. Tsinsen A1303&period; tree&lpar;伍一鸣&rpar; LCT

    LCT的各种操作... . cut link add mul size rev query 写的效率不够高... BZOJ上似乎TLE. ... A1303. tree(伍一鸣) 时间限制:2.5s  ...

  7. &lbrack;国家集训队2012&rsqb;middle

    http://cogs.pro:8080/cogs/problem/problem.php?pid=1763 二分答案x 把区间内>=x的数设为1,<x的数设为-1 左端点在[a,b]之间 ...

  8. luogu P2619 &lbrack;国家集训队2&rsqb;Tree I

    题目链接 luogu P2619 [国家集训队2]Tree I 题解 普通思路就不说了二分增量,生成树check 说一下坑点 二分时,若黑白边权有相同,因为权值相同优先选白边,若在最有增量时出现黑白等 ...

  9. &lbrack;国家集训队2012&rsqb;JZPFAR

    [国家集训队2012]JZPFAR 题目 平面上有n个点.现在有m次询问,每次给定一个点(px, py)和一个整数k,输出n个点中离(px, py)的距离第k大的点的标号.如果有两个(或多个)点距离( ...

  10. P2619 &lbrack;国家集训队2&rsqb;Tree I(最小生成树&plus;二分)

    P2619 [国家集训队2]Tree I 每次二分一个$x$,每条白边加上$x$,跑最小生成树 统计一下满足条件的最小值就好了. to me:注意二分不要写挂 #include<iostream ...

随机推荐

  1. Java定时任务Timer、TimerTask与ScheduledThreadPoolExecutor详解

     定时任务就是在指定时间执行程序,或周期性执行计划任务.Java中实现定时任务的方法有很多,本文从从JDK自带的一些方法来实现定时任务的需求. 一.Timer和TimerTask  Timer和Tim ...

  2. Ajax-jQuery实现

    load方法: 对上一篇中的javascript原生实现(数据格式为html),用jqury的post方法进行改造:  下面这句中“h2 a”,实现了对返回内容的选择:  $.get()\$.post ...

  3. DNA Sorting--hdu1379

    DNA Sorting Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total ...

  4. SpringCloud的Bus(一)消息中间件的概念和用途

    一.概念与定义 1.Message Broker Message Broker是一种消息验证.消息转换.消息路由的架构模式,用于如: 消息路由到一个或多个目的地 消息转化为其他的表现方式 执行消息的聚 ...

  5. 一个 redis 异常访问引发 oom 的案例分析

    「推断的前提是以事实为依据.」 这两天碰到一个线上系统的偶尔出现突然堆内存暴涨,这倒不是个什么疑难杂症, 只是过程中有些思路觉得可以借鉴参考,故总结下并写下来. 现象 内存情况可以看看下面这张监控图. ...

  6. netty入门demo(一)

    目录 前言 正文 代码部分 服务端 客服端 测试结果一: 解决粘包,拆包的问题 总结 前言 最近做一个项目: 大概需求: 多个温度传感器不断向java服务发送温度数据,该传感器采用socket发送数据 ...

  7. jQuery合并同一列中相同文本的相邻单元格

    一.效果图 二.在html的head中引入jQuery <script language="javascript" src="${pageContext.reque ...

  8. PAT A1024 Palindromic Number (25 分)——回文,大整数

    A number that will be the same when it is written forwards or backwards is known as a Palindromic Nu ...

  9. mysql自增主键

    MariaDB [test]> create table test1(id int primary key auto_increment,name varchar(20))auto_increm ...

  10. oracle误删数据

    表名:SYS_MENU alter table SYS_MENU enable row movementflashback table SYS_MENU to timestamp to_timesta ...