[JZOJ5984] 仙人掌

Description

Solution

标算我并不会...

考虑一种根号思想

首先以 \(1\) 为根dfs整棵树

那么在任意时刻一个点的儿子的权值种类最多只会有 \(\sqrt m\) 种。

可以在每个点维护一个邻接表，存储这个点的儿子们的所有权值种类，以及该权值出现次数。

考虑如何支持修改

如果要对点 \(x\) 进行修改

首先要改它的父亲 \(fa\)，就要找到它父亲的父亲 \(y\) ，因为 \(fa\) 是 \(y\) 的儿子，\(fa\) 的信息储存在了 \(y\) 邻接表里。

具体是在 \(y\) 的邻接表中找到 \(fa\) 当前的权值 \(val\)，然后把这个点的出现次数 \(-1\)。再把 \(val+1\) 的出现次数 \(+1\)。这样就完成了对 \(fa\) 权值的修改。

然后改点 \(x\) 的所有儿子就比较方便了，直接遍历 \(x\) 的邻接表，把所有点的权值 \(+1\) 就好了。

看上去就做完了，但是我们还不能支持查询任意一个点当前的权值。因为邻接表存的是一个个"等价类"，是无法区分具体的点的。

所以我们还需要在每个点维护两个标记方便我们快速知道真正的点权，具体是维护 \(tag[i],tag2[i]\) 分别表示修改过点 \(i\) 的儿子们多少次和点 \(i\) 的儿子们修改过多少次。这样 \(tag[i]+tag2[i]\) 就是点 \(i\) 的真实权值了。

时间复杂度 \(O(m\sqrt m)\) 但远远达不到上界。

Code

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using std::min;
using std::max;
using std::swap;
using std::vector;
typedef double db;
typedef long long ll;
#define pb(A) push_back(A)
#define pii std::pair<int,int>
#define all(A) A.begin(),A.end()
#define mp(A,B) std::make_pair(A,B)
const int N=5e5+5;
const ll mod=1000109107;

ll tot=0;
int tag[N],tag2[N];
int n,m,son[N],fa[N];

struct Edge{
    int to,nxt,sze;
};

struct G{
    int dp[N],dc;
    int head[N],cnt;
    Edge edge[N*20];

    void del(int x){
        dp[++dc]=x;
    }

    int newnode(){
        return dc?dp[dc--]:++cnt;
    }

    void add(int x,int y,int z=0){
        int t=newnode();
        edge[t].to=y;
        edge[t].nxt=head[x];
        edge[t].sze=z;
        head[x]=t;
    }

}A,B;

int getint(){
    int X=0,w=0;char ch=getchar();
    while(!isdigit(ch))w|=ch=='-',ch=getchar();
    while( isdigit(ch))X=X*10+ch-48,ch=getchar();
    if(w) return -X;return X;
}

void dfs(int now){
    for(int i=A.head[now];i;i=A.edge[i].nxt){
        int to=A.edge[i].to;
        if(to==fa[now]) continue;
        fa[to]=now;son[now]++;
        dfs(to);
    }
}

signed main(){
    freopen("cactus.in","r",stdin);freopen("cactus.out","w",stdout);
    n=getint(),m=getint();
    for(int i=1;i<n;i++){
        int x=getint(),y=getint();
        A.add(x,y),A.add(y,x);
    } dfs(1);
    fa[1]=n+1;son[n+1]=1;
    for(int i=1;i<=n+1;i++)
        if(son[i])
            B.add(i,0,son[i]);
    for(int cas=1;cas<=m;cas++){
        int x=getint(),ans=0;
        if(x>1){
            int y=fa[fa[x]],val=tag[y]+tag2[fa[x]];
            for(int las=0,i=B.head[y];i;las=i,i=B.edge[i].nxt){
                if(B.edge[i].to==val){
                    if(B.edge[i].sze>1)
                        B.edge[i].sze--;
                    else if(las)
                        B.edge[las].nxt=B.edge[i].nxt,B.del(i);
                    else
                        B.head[y]=B.edge[i].nxt,B.del(i);
                    break;
                }
            } ans=val+1;
            int flag=0;
            for(int i=B.head[y];i;i=B.edge[i].nxt){
                if(B.edge[i].to==ans){
                    B.edge[i].sze++;
                    flag=1; break;
                }
            } if(!flag)
                B.add(y,ans,1);
        } for(int i=B.head[x];i;i=B.edge[i].nxt){
            B.edge[i].to++;
            if(B.edge[i].sze&1) ans^=B.edge[i].to;
        } (tot+=1ll*ans*((1ll*cas*cas%mod+cas)%mod)%mod)%=mod;
        tag[x]++;tag2[fa[x]]++;
    } printf("%lld\n",tot);
    return 0;
}