编程知识 cdmana.com

一道洛谷的题目,来康康

题目描述
一棵 nn 个点的树,每个点的初始权值为 11。
对于这棵树有 qq 个操作,每个操作为以下四种操作之一:

  • u v c:将 uu 到 vv 的路径上的点的权值都加上自然数 cc;
  • u1 v1 u2 v2:将树中原有的边 (u_1,v_1)(u
    1

    ,v
    1

    ) 删除,加入一条新边 (u_2,v_2)(u
    2

    ,v
    2

    ),保证操作完之后仍然是一棵树;
  • u v c:将 uu 到 vv 的路径上的点的权值都乘上自然数 cc;

/ u v:询问 uu 到 vv 的路径上的点的权值和,将答案对 5106151061 取模。

输入格式
第一行两个整数 n,qn,q

接下来 n-1n−1 行每行两个正整数 u,vu,v,描述这棵树的每条边。

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

输出格式
对于每个询问操作,输出一行一个整数表示答案。

输入输出样例
输入 #1复制
3 2
1 2
2 3

  • 1 3 4
    / 1 1
    输出 #1复制
    4
    说明/提示
    【数据范围】
    对于 10%10% 的数据,1\le n,q \le 20001≤n,q≤2000;
    另有 15%15% 的数据,1 \le n,q \le 5\times 10^41≤n,q≤5×10
    4
    ,没有 - 操作,并且初始树为一条链;
    另有 35%35% 的数据,1 \le n,q \le 5\times 10^41≤n,q≤5×10
    4
    ,没有 - 操作;
    对于 100%100% 的数据,1\le n,q \le 10^51≤n,q≤10
    5
    ,0\le c \le 10^40≤c≤10
    4



采纳答案:

LCT啊,我会了

#include<cstdio>#include<cstdlib>#define R register unsigned int#define I inline#define YL 51061#define lc c[x][0]#define rc c[x][1]#define mul(x) x*=c;x%=YL#define add(x,c) x+=c;x%=YL#define G ch=getchar()#define gc G;while(ch<'*')G#define in(z) gc;z=ch&15;G;while(ch>'*')z*=10,z+=ch&15,G;const int N=100009;unsigned int n,f[N],c[N][2],v[N],s[N],sz[N],lm[N],la[N],st[N];bool r[N];I bool nroot(R x){//好像Dalao都写的是isroot    return c[f[x]][0]==x||c[f[x]][1]==x;}I void pushup(R x){    s[x]=(s[lc]+s[rc]+v[x])%YL;    sz[x]=sz[lc]+sz[rc]+1;}I void pushr(R x){//翻转    R t=lc;lc=rc;rc=t;r[x]^=1;}I void pushm(R x,R c){//乘    mul(s[x]);mul(v[x]);mul(lm[x]);mul(la[x]);}I void pusha(R x,R c){//加    add(s[x],c*sz[x]);add(v[x],c);add(la[x],c);}I void pushdown(R x){    if(lm[x]!=1)pushm(lc,lm[x]),pushm(rc,lm[x]),lm[x]=1;    if(la[x])   pusha(lc,la[x]),pusha(rc,la[x]),la[x]=0;    if(r[x])   {if(lc)pushr(lc);if(rc)pushr(rc);r[x]=0;}}I void rotate(R x){    R y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];    if(nroot(y))c[z][c[z][1]==y]=x;c[x][!k]=y;c[y][k]=w;//注意if(nroot(y)),本蒟蒻经常忘写    if(w)f[w]=y;f[y]=x;f[x]=z;    pushup(y);}I void splay(R x){    R y=x,z=0;    st[++z]=y;//手动放个栈    while(nroot(y))st[++z]=y=f[y];    while(z)pushdown(st[z--]);    while(nroot(x)){        y=f[x];z=f[y];        if(nroot(y))            rotate((c[y][0]==x)^(c[z][0]==y)?x:y);        rotate(x);    }    pushup(x);}I void access(R x){    for(R y=0;x;x=f[y=x])        splay(x),rc=y,pushup(x);}I void makeroot(R x){    access(x);    splay(x);    pushr(x);}I void split(R x,R y){    makeroot(x);    access(y);    splay(y);}I void link(R x,R y){    makeroot(x);f[x]=y;}I void cut(R x,R y){    split(x,y);f[x]=c[y][0]=0;}int main(){    register char ch;    R q,i,a,b,k;    in(n);in(q);    for(i=1;i<=n;++i)v[i]=sz[i]=lm[i]=1;//注意乘法标记的初值为1    for(i=1;i<n;++i){        in(a);in(b);        link(a,b);    }    while(q--){        gc;        switch(ch){        case '+':            in(a);in(b);in(k);            split(a,b);pusha(b,k);            break;        case '-':            in(a);in(b);cut(a,b);            in(a);in(b);link(a,b);            break;        case '*':            in(a);in(b);in(k);            split(a,b);pushm(b,k);            break;        case '/':            in(a);in(b);            split(a,b);            printf("%d\n",s[b]);        }    }    return 0;}


其他答案2:

你这自问自答。。。。

版权声明
本文为[CSDN问答]所创,转载请带上原文链接,感谢
https://ask.csdn.net/questions/7493262

Scroll to Top