CF GYM102759 I. Query On A Tree 17

(Updated: )
oi
, , ,

Description

题目链接：GYM102759 I

给定一棵以 $1$​ 为根节点的拥有 $N$​ 个节点的带点权树，初始时每个点的点权均为 $0$​，有 $Q$​ 次操作，每次操作有两种类型：

  • 1 u，以 $u$ 为根节点的子树内每个点点权均加 $1$。
  • 2 u v，将节点 $u$ 到节点 $v$ 的简单路径上的点的点权均加 $1$。

每次操作后询问使 $\sum_{y=1}^N A_y\times dist(x,y)$​ 最小的 $x$，其中 $dist(x,y)$ 表示点 $x$ 到点 $y$ 的路径上的边数，如果有多个，请输出离根节点 $1$ 最近的那个。

$N,Q\leq 10^5$。

Solution

显然最后的答案就是求带权重心。

那么我们相当于求深度最浅的重心。

对于一个点 $v$，如果它是答案，把它作为根，那么 $root$ 所在的子树大小 $\leq$ 权值和的一半，也就是说剩下的大小（以 $root$ 为根时子树 $v$ 的大小）$\ge$ 权值和的一半，也就是说中位数一定包含在 $v$ 所包含的子树里。

直接上轻重链剖分，可以线段树上二分求出中位数，每次倍增向上跳，判一下是否符合条件即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=1e5+10;
int n,m,fir[N],nxt[N<<1],son[N<<1],tot,dep[N],f[N][21],sz[N],mx[N],dfn[N],top[N],bk[N],cnt;
I void Add(CI x,CI y){nxt[++tot]=fir[x],fir[x]=tot,son[tot]=y;}
#define to son[i]
I void Dfs1(CI x,CI fa){RI i;for(dep[x]=dep[f[x][0]=fa]+(sz[x]=1),i=fir[x];i;i=nxt[i]) to^fa&&(Dfs1(to,x),sz[x]+=sz[to],sz[mx[x]]<sz[to]&&(mx[x]=to));}
I void Dfs2(CI x,CI Top){
    if(top[x]=Top,bk[dfn[x]=++cnt]=x,mx[x]) Dfs2(mx[x],Top);
    RI i;for(i=fir[x];i;i=nxt[i]) to^f[x][0]&&to^mx[x]&&(Dfs2(to,to),0);
}
class SegmentTree{
    private:
        LL T[N<<2],tg[N<<2];
        #define mid (l+r>>1)
        #define PT CI x=1,CI l=1,CI r=n
        #define LT x<<1,l,mid
        #define RT x<<11,mid+1,r
        #define PU(x) (T[x]=T[x<<1]+T[x<<11])
        I void PD(CI x,CI l,CI r){tg[x]&&(T[x<<1]+=tg[x]*(mid-l+1),tg[x<<1]+=tg[x],T[x<<11]+=tg[x]*(r-mid),tg[x<<11]+=tg[x],tg[x]=0);}
    public:
        I void U(CI L,CI R,CI v,PT){
            if(L<=l&&r<=R) return T[x]+=v*(r-l+1),tg[x]+=v,void();
            PD(x,l,r),L<=mid&&(U(L,R,v,LT),0),R>mid&&(U(L,R,v,RT),0),PU(x);
        }
        I LL Q(CI L,CI R,PT){
            if(L<=l&&r<=R) return T[x];
            LL S=0;return PD(x,l,r),L<=mid&&(S+=Q(L,R,LT)),R>mid&&(S+=Q(L,R,RT)),S;
        }
        I int G(LL k,PT){
            if(l==r) return bk[l];
            return PD(x,l,r),T[x<<1]>=k?G(k,LT):G(k-T[x<<1],RT);
        }
        I LL S(){return T[1];}
}T;
I void U(RI x,RI y){
    W(top[x]^top[y]) dep[top[x]]<dep[top[y]]&&(swap(x,y),0),T.U(dfn[top[x]],dfn[x],1),x=f[top[x]][0];
    dfn[x]>dfn[y]&&(swap(x,y),0),T.U(dfn[x],dfn[y],1);
}
I int Q(){
    LL k=T.S()/2+1;RI j,i=T.G(k);
    if(T.Q(dfn[i],dfn[i]+sz[i]-1)>=k) return i;
    for(j=20;~j;j--) if(f[i][j]&&T.Q(dfn[f[i][j]],dfn[f[i][j]]+sz[f[i][j]]-1)<k) i=f[i][j];
    return f[i][0];
}
int main(){
    RI i,j,o,x,y;for(read(n),i=1;i<n;i++) read(x,y),Add(x,y),Add(y,x);for(Dfs1(1,0),Dfs2(1,1),j=1;j<=20;j++) for(i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1];
    for(read(m);m--;) read(o,x),o&1?T.U(dfn[x],dfn[x]+sz[x]-1,1):(read(y),U(x,y)),writeln(Q());return 0;
}