题目概述

有 $n$ 个点的带边权树和 $m$ 次操作，每次操作：1.将一个点变成黑色。2.求 $x$ 到所有黑色点的距离。

解题报告

好像可以大力点分树……我没有想过。考虑我们要求的是 $\sum dis_x+dis_y-2dis_{LCA(x,y)}$ ，其中前面两个是很好求的，问题就是 $\sum dis_{LCA(x,y)}$ 怎么求。

考虑只有一个黑点的时候，我们把黑点到根的边都标记一次（每标记一次，就加上一次边权），然后询问 $x$ 到根的权值和，由于 $LCA(x,y)$ 是 $x,y$ 的最近公共祖先，所以会从 $LCA(x,y)$ 开始统计，这正好就是 $dis_{LCA(x,y)}$ ！

所以只需要简单的路径加操作就行了，可以用LCT（出现了，一只 $log_2n$ LCT跑不过两只 $log_2n$ 链剖线段树）。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100000,maxm=100000,maxt=maxn+maxm;

int n,te,p[maxn+5],val[maxt+5],fa[maxt+5],son[maxt+5][2];bool vis[maxn+5];
int cnt[maxt+5],B;LL sum[maxt+5],num[maxt+5],dis[maxn+5],S;bool flip[maxt+5];int tag[maxt+5];

#define is_ro(p) (son[fa[p]][0]!=(p)&&son[fa[p]][1]!=(p))
#define Son(p) ((p)==son[fa[p]][1])
class TreeColoring{
public:
    int curValue,threshold,maxDist,queryType[maxn+5],queryNode[maxn+5];
    inline void Pushup(int p){
        sum[p]=sum[son[p][0]]+val[p]+sum[son[p][1]];
        num[p]=num[son[p][0]]+(LL)val[p]*cnt[p]+num[son[p][1]];
    }
    inline void Rotate(int t){
        int p=fa[t],d=Son(t);son[p][d]=son[t][d^1];son[t][d^1]=p;
        if (!is_ro(p)) son[fa[p]][Son(p)]=t;Pushup(p);Pushup(t);
        if (son[p][d]) fa[son[p][d]]=p;fa[t]=fa[p];fa[p]=t;
    }
    inline void Addflip(int p) {swap(son[p][0],son[p][1]);flip[p]^=1;}
    inline void Addtag(int p,int k) {cnt[p]+=k;num[p]+=sum[p]*k;tag[p]+=k;}
    inline void Pushdown(int p){
        if (flip[p]) Addflip(son[p][0]),Addflip(son[p][1]),flip[p]^=1;
        if (tag[p]) Addtag(son[p][0],tag[p]),Addtag(son[p][1],tag[p]),tag[p]=0;
    }
    inline void Splay(int p){
        static int top,stk[maxt+5];stk[top=1]=p;
        for (int i=p;!is_ro(i);i=fa[i]) stk[++top]=fa[i];
        while (top) Pushdown(stk[top--]);
        for (int pre=fa[p];!is_ro(p);Rotate(p),pre=fa[p])
            if (!is_ro(pre)) Rotate(Son(pre)==Son(p)?pre:p);
    }
    inline void Access(int p) {for (int lst=0;p;lst=p,p=fa[p]) Splay(p),son[p][1]=lst,Pushup(p);}
    inline void Makero(int x) {Access(x);Splay(x);Addflip(x);}
    inline void Link(int x,int y) {Makero(x);Makero(y);fa[x]=y;}
    inline void Update(int x) {Makero(1);Access(x);Splay(x);Addtag(x,1);}
    inline LL Dis(int x) {Makero(1);Access(x);Splay(x);return sum[x];}
    inline LL Ask(int x) {Makero(1);Access(x);Splay(x);return num[x];}
    inline int genNextRandom() {curValue=(curValue*1999+17)%1000003;return curValue;}
    inline void generateInput(){
        for (int i=1;i<n;i++){
            val[n+i]=genNextRandom()%maxDist;Pushup(n+i);
            int x=genNextRandom();x<threshold?x=i:x=x%i+1;Link(i+1,n+i);Link(x,n+i);
        }for (int i=1;i<=te;i++) queryType[i]=genNextRandom()%2+1,queryNode[i]=genNextRandom()%n+1;
    }
    inline LL color(int a,int b,int c,int d,int e,LL ans=0){
        n=a;te=b;curValue=c;threshold=d;maxDist=e;generateInput();
        for (int i=1;i<=n;i++) dis[i]=Dis(i);
        for (int i=1;i<=te;i++){
            int tp=queryType[i],x=queryNode[i];
            if (tp==2) ans^=S+(LL)B*dis[x]-(Ask(x)<<1);
            else if (!vis[x]) B++,S+=dis[x],Update(x),vis[x]=true;
        }return ans;
    }
};