来自今日模拟赛吴爷爷出的题

题目描述

$ZSGW$ 已经陪伴你们两天了，这两天时间，聪明的你们帮助他解决了许多的问题，为了感激你们的付出，$ZSGW$决定举办一次烤肉派对。
$ZSGW$ 虽然脑子不太灵光，烤肉倒是有那么两下子。他最拿手的就是蜜汁叉烧肉。一般的叉烧肉，都是在一根铁签子上串肉，但是 $ZSGW$ 的烤肉叉不一样，
​
他将其命名为“铁树肉林”——顾名思义，这个烤肉叉的形状是一棵树，有$ n$个钩子，每个钩子上都可以挂一块叉烧肉。$n$个钩子之间用$n-1$ 条铁签相连,烤肉时，在每个钩子上挂上新鲜的猪里脊肉，刷上秘制蜜汁，送入烤炉即可。
​
烤叉烧肉，关键在于蜜汁的涂抹。$ZSGW$ 的树形烤肉叉使用起来很有讲究，刷蜜汁时，$ZSGW$ 需要用手捏住一个钩子，举起整串肉，我们把拎起肉之后，对于每块肉， 挂在它下面的肉都称为这块肉下面的肉。 如图所示， 手捏的部位不同，整串肉的形状以及每块肉下面的肉都会发生变化。

$ZSGW$ 在拎起整串肉之后，会指定一块肉，将它以及下面的所有肉刷上若干层蜜汁。为了涂抹均匀，他也会不停地切换捏的部位。有时候，他也会只在一块肉上，刷上若干层蜜汁。一开始的时候肉上都没有蜜汁。一串肉的美味度是整串肉上蜜汁层数的平均值。

在刷蜜汁的过程中，为了让肉更好吃，$ZSGW$ 会不断地问你某块肉下面的所有肉的美味度，如果你能准确回答他提出的所有问题，等到烤肉好了，
​
$ZSGW$ 以及他的老大——$WK$ 就会亲自请你大吃一顿
你想吃烤肉吗？

输入格式

输入文件的第一行，包含两个整数$n$,$m$。表示肉的总数以及事件的个数。

接下来共有$n-1$行，每行两个整数 $b$ $a$，表示$a$和$b$是直接相连的。接下来$m$行，每行描述一个事件，格式分别如下：

1 $x_i$ ：这表示 $ZSGW$ 改变了手拎的部位，现在 $ZSGW$ 从 $x_i $处拎起了整串肉。
​
2 $ x$ $y$ ：这表示$ZSGW$将肉$x $以及它下面的所有肉刷上了 $y$ 层蜜汁。
​
3 $x $ $y $：这表示$ ZSGW$ 选择了肉 $x $，给它刷上了 y 层蜜汁。
​
4 $ x $：表示 $ZSGW$ 提出了一个询问：肉 $x$ 以及它下面的所有肉的美味度是多少？

输出格式

输出包含若干行，表示对于每个询问的答案。每行的格式为$“ x/y ”$，即答案的既约分数的形式，若答案为0，请输出$“0/1”$。

题解

首先，树链剖分+线段树是非常显然的

这道题题目中关于根的旋转，其实并不用旋转，这是重点

我们可以发现当只有与$root$在往上面链上面的一串点才会受到影响

$lca(x,root)!=x$时，说明x在root子树中没有影响
当$lca(x,root)=x$时
若$x=root$，此时就是整个树
若$x!=root$，$son[x]=son[1]-son[s]$;
此时$s$就是$root$到$x$的链上离$x$最近的一个点

然而$s$就需要倍增了

代码

虽然比较长但比较好理解

#include <bits/stdc++.h>
#define N 500000+110
#define lson 2*p
#define rson 2*p+1
#define ll long long
using namespace std;
int n,m,cnt,root,op,top[N],son[N],tot;
int head[N],dfn[N],pos[N],sizee[N],deep[N],fa[N][30];
//--------------------树链剖分求lca以及倍增求路径上的点--------------------------------------------
struct node
{
    int nt=-1,to;
}edge[N*2];
void add(int x,int y)
{
    cnt++;
    edge[cnt].to=y;
    edge[cnt].nt=head[x];
    head[x]=cnt;
}
void dfs(int x,int fa1,int d)
{
    deep[x]=d;sizee[x]=1;
    fa[x][0]=fa1;
    for(int i=1;(1<<i)<deep[x];i++)
        fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int i=head[x];i!=-1;i=edge[i].nt)
    {
        int v=edge[i].to;
        if(v==fa1)continue;
        dfs(v,x,d+1);
        sizee[x]+=sizee[v];
        if(sizee[v]>sizee[son[x]])son[x]=v;

    }
}
void dfs2(int x,int tp)
{
    pos[x]=++tot;top[x]=tp;
    if(!son[x])return ;
    dfs2(son[x],tp);
    for(int i=head[x];i!=-1;i=edge[i].nt)
    {
        int v=edge[i].to;
        if(v!=fa[x][0]&&v!=son[x])dfs2(v,v);
    }
}
int lca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(deep[top[x]]>deep[top[y]])x=fa[top[x]][0];
        else y=fa[top[y]][0];
    }
    if(deep[x]>deep[y])return y;
    else return x;
}
int find_son(int x,int y)
{
    for(int i=20;i>=0;i--)
        if((1<<i)<=deep[x]&&deep[fa[x][i]]>deep[y])
          x=fa[x][i];
    return x;
}
//------------------------线段树----------------------------------------------------------------
struct tree
{
    int lt,rt;
    ll sum,val;
}t[N*4];
void pushup(int p)
{
    t[p].sum=t[lson].sum+t[rson].sum;
}
void build(int p,int l,int r)
{
    t[p].rt=r;t[p].lt=l;
    if(l==r){t[p].sum=0;return ;}
    int mid=(l+r)/2;
    build(lson,l,mid);
    build(rson,mid+1,r);
    pushup(p);
}
void pushdown(int p)
{
    if(t[p].val!=0)
    {
        t[lson].val+=t[p].val;
        t[rson].val+=t[p].val;
        t[lson].sum+=(t[lson].rt-t[lson].lt+1)*t[p].val;
        t[rson].sum+=(t[rson].rt-t[rson].lt+1)*t[p].val;
        t[p].val=0;
    }
}
void add(int p,int l,int r,ll d)
{
    if(t[p].lt==l&&t[p].rt==r){t[p].val+=d;t[p].sum+=(r-l+1)*d;return ;}
    pushdown(p);
    int mid=(t[p].lt+t[p].rt)/2;
    if(r<=mid)add(lson,l,r,d);
    else if(l>mid)add(rson,l,r,d);
    else add(lson,l,mid,d),add(rson,mid+1,r,d);
    pushup(p);
}
ll query(int p,int l,int r)
{
    if(t[p].rt==r&&t[p].lt==l)return t[p].sum;
    pushdown(p);
    int mid=(t[p].lt+t[p].rt)/2;
    if(r<=mid)return query(lson,l,r);
    else if(l>mid)return query(rson,l,r);
    else return query(lson,l,mid)+query(rson,mid+1,r);
}
//---------------操作----------------------------------------------------------
ll gcd(ll a,ll b)
{
    return !b?a:gcd(b,a%b);
}
void upson(int x,ll k)
{
    if(lca(x,root)!=x)add(1,pos[x],pos[x]+sizee[x]-1,k);
    else
    {
        if(x==root)add(1,1,n,k);
        else
        {
            add(1,1,n,k);
            int s=find_son(root,x);
            add(1,pos[s],pos[s]+sizee[s]-1,-k);
        }
    }
}
void update(int x,ll k)
{
    add(1,pos[x],pos[x],k);
}
void qson(int x)
{
    ll ans,ans1;
    if(lca(x,root)!=x)
        ans=query(1,pos[x],pos[x]+sizee[x]-1),ans1=sizee[x];
    else
    {
        if(x==root)
            ans=query(1,1,n),ans1=sizee[1];
        else
        {
            int s=find_son(root,x);
            ans=query(1,1,n)-query(1,pos[s],pos[s]+sizee[s]-1),ans1=sizee[1]-sizee[s];

        }

    }
    ll gcdd=(gcd(ans,ans1));
        if(ans1==0)
            printf("0/1\n");
        else
            printf("%lld/%lld\n",ans/gcdd,ans1/gcdd);

}
//---------------主函数--------------------------------------------------------------------
int main()
{
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
       add(x,y);add(y,x);
    }
    dfs(1,0,1);
    dfs2(1,1);
    build(1,1,n);
   for(int i=1;i<=m;i++)
   {
       int op,x;
       ll y;
       scanf("%d",&op);
       switch(op)
       {
           case 1:scanf("%d",&root);break;
           case 2:scanf("%d%lld",&x,&y);upson(x,y);break;
           case 3:scanf("%d%lld",&x,&y);update(x,y);break;
           case 4:scanf("%d",&x);qson(x);break;
       }

   }
    return 0;
}