洛谷P1501 [国家集训队]Tree II(LCT)

题目描述

一棵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的余数。

输入输出格式

输入格式:

第一行两个整数n,q

接下来n-1行每行两个正整数u,v,描述这棵树

接下来q行,每行描述一个操作

输出格式:

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

输入输出样例

输入样例#1: 复制

3 2
1 2
2 3
* 1 3 4
/ 1 1

输出样例#1: 复制

4

说明

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

By (伍一鸣)

全程自己YY,调了一下午真累啊QWQ......

LCT的板子题,要维护子树和,加法标记,乘法标记和自身的值

放标记的时候先放乘法标记

至于为什么http://www.cnblogs.com/zwfymqz/p/8588693.html

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long 
const int mod = 51061; 
using namespace std;
const int MAXN = 1e5+10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
    return x * f;
}
int N, Q;
#define ls(x) T[x].ch[0]
#define rs(x) T[x].ch[1]
#define fa(x) T[x].f
struct node {
    int f, ch[2], r, mul, add, siz, sum, val;
}T[MAXN];
bool IsRoot(int x) {
    return T[fa(x)].ch[0] != x && T[fa(x)].ch[1] != x;
}
int ident(int x) {
    return T[fa(x)].ch[0] == x ? 0 : 1;
}
void connect(int x, int fa, int how) {
    T[x].f = fa;
    T[fa].ch[how] = x;
}
void update(int x) {
    T[x].sum = (T[ls(x)].sum + T[rs(x)].sum + T[x].val ) % mod;
    T[x].siz = T[ls(x)].siz + T[rs(x)].siz + 1 ;
}
void rotate(int x) {
    int Y = fa(x), R = fa(Y), Yson = ident(x), Rson = ident(Y);
    int B = T[x].ch[Yson ^ 1];
    T[x].f = R;
    if(!IsRoot(Y)) 
        connect(x, R, Rson);
    connect(B, Y, Yson);
    connect(Y, x, Yson ^ 1);
    update(Y);update(x);
}
void pushr(int x) {
    if(T[x].r) {
        swap(ls(x), rs(x));
        T[ls(x)].r ^= 1;
        T[rs(x)].r ^= 1;
        T[x].r = 0;
    }
}
void pushmul(int x) {
    T[ls(x)].val *= T[x].mul; T[ls(x)].val %= mod;
    T[rs(x)].val *= T[x].mul; T[rs(x)].val %= mod;
    T[ls(x)].sum *= T[x].mul; T[ls(x)].sum %= mod;
    T[rs(x)].sum *= T[x].mul; T[rs(x)].sum %= mod;
    T[ls(x)].add *= T[x].mul; T[ls(x)].add %= mod;
    T[rs(x)].add *= T[x].mul; T[rs(x)].add %= mod;
    T[ls(x)].mul *= T[x].mul; T[ls(x)].mul %= mod;
    T[rs(x)].mul *= T[x].mul; T[rs(x)].mul %= mod;
    T[x].mul = 1;
}
void pushadd(int x) {
    T[ls(x)].val += T[x].add; T[ls(x)].val %= mod;
    T[rs(x)].val += T[x].add; T[rs(x)].val %= mod;
    T[ls(x)].sum += T[ls(x)].siz * T[x].add; T[ls(x)].sum %= mod;
    T[rs(x)].sum += T[rs(x)].siz * T[x].add; T[rs(x)].sum %= mod;
    T[ls(x)].add += T[x].add; T[ls(x)].add %= mod;
    T[rs(x)].add += T[x].add; T[rs(x)].add %= mod;
    T[x].add = 0;
}
void pushdown(int x) {
    pushr(x);
    pushmul(x);
    pushadd(x);
}
int st[MAXN];
int fuck;
void splay(int x) {
    int y = x, top = 0;
    st[++top] = y;
    while(!IsRoot(y)) st[++top] = (y = fa(y));
    while(top) pushdown(st[top--]);
    for(int y = fa(x); !IsRoot(x); rotate(x), y = fa(x))
        if(!IsRoot(y))
            rotate( ident(x) == ident(y) ? y : x );
}
void access(int x) {
    for(int y = 0; x; x = fa(y = x))//tag
        splay(x), rs(x) = y, update(x);
}
void makeroot(int x) {
    access(x); 
    splay(x);
    T[x].r ^= 1;
}
void split(int x,int y) {
    makeroot(x);
    access(y);
    splay(y);
}
void link(int x, int y) {
    makeroot(x);
    T[x].f = y;
}
int findroot(int x) {
    access(x); 
    splay(x);
    while(ls(x)) x = ls(x);
    return x;
}
void cut(int x, int y) {
    split(x, y);
    //makeroot(x);
    if(findroot(y) == x && fa(x) == y && !rs(x))
        T[x].f = T[y].ch[0] = 0, update(y);
}
main() {
    freopen("a.in","r",stdin);
    scanf("%lld%lld", &N, &Q);
    for(int i = 1; i <= N; i++) 
        T[i].val = 1, T[i].sum = 1, T[i].mul = 1, T[i].siz = 1, T[i].add = 0;
    for(int i = 1; i <= N - 1; i++) {
        int x = read(), y = read();
        link(x, y);
    }
    int fuck = 0;
    while(Q--) {
        char c = 0; int u1, v1, u2, v2, val;
        while(c < '*') c = getchar(); 
        scanf("%lld%lld", &u1, &v1);
        if(c == '+') {
            scanf("%lld", &val);
            split(u1, v1);
            T[v1].val += val; T[v1].val %= mod;
            T[v1].add += val; T[v1].add %= mod;
            T[v1].sum += T[v1].siz * val; T[v1].sum %= mod;
        }    
        else if(c == '-') {
            scanf("%lld%lld", &u2, &v2);
            cut(u1, v1);
            link(u2, v2);
        }
        else if(c == '/') {
            split(u1, v1);
            printf("%d\n",T[v1].sum%mod);            
        }
        else {
            scanf("%lld",&val);
            split(u1, v1);
            T[v1].val *= val; T[v1].val %= mod;
            T[v1].sum *= val; T[v1].siz %= mod;
            T[v1].add *= val; T[v1].add %= mod;
            T[v1].mul *= val; T[v1].mul %= mod;
        }    
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java爬坑系列

【Java入门提高篇】Day22 Java容器类详解(五)HashMap源码分析(上)

准备了很长时间,终于理清了思路,鼓起勇气,开始介绍本篇的主角——HashMap。说实话,这家伙能说的内容太多了,要是像前面ArrayList那样翻译一下源码,稍...

26250
来自专栏陈树义

如何检测链表中存在的环

链表有环的定义是,链表的尾节点指向了链接中间的某个节点。比如下图,如果单链表有环,则在遍历时,在通过结点J之后,会重新回到结点D。 ? 看了上面的定义之后,如...

30860
来自专栏数据结构与算法

LOJ#6283. 数列分块入门 7

内存限制:256 MiB时间限制:500 ms标准输入输出 题目类型:传统评测方式:文本比较 上传者: hzwer 提交提交记录统计讨论测试数据 题目描述 给出...

373140
来自专栏数据结构与算法

#106. 二逼平衡树(附带详细代码注释)

内存限制:512 MiB时间限制:4000 ms标准输入输出 题目类型:传统评测方式:文本比较 上传者: 匿名 提交提交记录统计讨论测试数据 题目描述 这是一道...

41370
来自专栏Java成神之路

Java_util_02_Java判断字符串是中文还是英文

做微信开发,使用百度翻译API时,需要指定译文的语种。这就需要我们判断待翻译内容是中文还是英文,若是中文,则翻译成英文,若是英文则翻译成中文。

14650
来自专栏owent

POJ PKU 2549 Sumsets 解题报告

题目链接http://acm.pku.edu.cn/JudgeOnline/problem?id=2549

10310
来自专栏包子铺里聊IT

劳动最光荣!Double Letter Problem from TopCoder

包子IT面试培训 助你拿到理想的offer! 这是TopCoder上面一道比较简单的250分的题目,非常适合作为面试的第一道热身题目,考察了面试者对于基本的数据...

29860
来自专栏数据结构与算法

洛谷P1852 奇怪的字符串

题目描述 输入两个01串,输出它们的最长公共子序列的长度 输入输出格式 输入格式: 一行,两个01串 输出格式: 最长公共子序列的长度 输入输出样例 输入样例#...

33390
来自专栏Java技术分享

泛形

一. 泛型概念的提出(为什么需要泛型)? 首先,我们看下下面这段简短的代码:

200100
来自专栏清墨_iOS分享

OpenGLES-02 绘制基本图元(点、线、三角形)

在绘制之前,我们需要了解下面的知识: 一、渲染管线 下图中展示整个OpenGL ES 2.0可编程渲染管线 ? 渲染管线.png 图中Vertex Shade...

41790

扫码关注云+社区

领取腾讯云代金券