Post

树链剖分

Posted
By 26 min read

五个概念

  • 重儿子：儿子中最大size的节点
  • 轻儿子：除重儿子外的儿子
  • 重边：连接重儿子的边
  • 轻边：连接轻儿子的边
  • 重链：重儿子往上走到根节点或者轻儿子的边(亦可以是一个轻儿子)

    题型

    对一棵树的路径进行大量的操作
    树链剖分即将每条重链分出来 $ (O(logN)条) $
    将节点按照先重儿子的dfs序排好,用线段树维护每个区间(重链)的信息
    $ 总复杂度：O(log^2 N ) $

    P3384 树链剖分模板

    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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

    struct node{
  ll l,r,add,sum;
} t[N<<2];
ll w[N],siz[N],id[N],nw[N],dep[N],top[N],par[N],son[N];
/*
w[i]是原来的值
siz[i]是树的大小
id[i]是dfs序编号
nw[i]是dfs序为i的值
dep[i]为高度
top[i]为当前i所在的重链的头部
par[i]为父节点
son[i]为重儿子
*/
ll n,m,r,mod;
vector<ll> adj[N];
void dfs1(int u,int fa){//预处理
  par[u]=fa;
  dep[u]=dep[fa]+1;
  siz[u]=1;
  for(auto v:adj[u]){
      if(v==fa)continue;
      dfs1(v,u);
      siz[u]+=siz[v];
      if(siz[son[u]]<siz[v])son[u]=v;
  }
}
int cnt=0;
void dfs2(int u,int t){//dfs序，重链头节点
  id[u]=++cnt;
  nw[cnt]=w[u];
  top[u]=t;
  if(!son[u])return;
  dfs2(son[u],t);
  for(auto v:adj[u]){
      if(v==par[u]||v==son[u])continue;
      dfs2(v,v);
  }
}
void pushup(int p){
  t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
void pushdown(int p){
  auto &u=t[p],&l=t[p<<1],&r=t[p<<1|1];
  l.sum+=u.add*(l.r-l.l+1);
  r.sum+=u.add*(r.r-r.l+1);
  l.add+=u.add;
  r.add+=u.add;
  u.add=0;
}
void build(int p,int l,int r){
  t[p]={l,r,0,nw[r]};
  if(l==r)return;
  int mid=l+r>>1;
  build(p<<1,l,mid);
  build(p<<1|1,mid+1,r);
  pushup(p);
}
void modify(int p,int l,int r,int k){
  if(l<=t[p].l&&r>=t[p].r){
      t[p].add+=k;
      t[p].sum+=k*(t[p].r-t[p].l+1);
      return;
  }
  pushdown(p);
  int mid=t[p].l+t[p].r>>1;
  if(l<=mid)modify(p<<1,l,r,k);
  if(r>mid)modify(p<<1|1,l,r,k);
  pushup(p);
}
ll query(int p,int l,int r){
  if(l<=t[p].l&&r>=t[p].r)return t[p].sum;
  pushdown(p);
  ll res=0;
  int mid=t[p].l+t[p].r>>1;
  if(l<=mid)res+=query(p<<1,l,r);
  if(r>mid)res+=query(p<<1|1,l,r);
  return res;
}
void modify_path(int u,int v,int k){
  while(top[u]!=top[v]){
      if(dep[top[u]]<dep[top[v]])swap(u,v);
      modify(1,id[top[u]],id[u],k);
      u=par[top[u]];
  }
  if(dep[u]<dep[v])swap(u,v);
  modify(1,id[v],id[u],k);
}
ll query_path(int u,int v){
  ll res=0;
  while(top[u]!=top[v]){
      if(dep[top[u]]<dep[top[v]])swap(u,v);
      res+=query(1,id[top[u]],id[u]);
      u=par[top[u]];
  }
  if(dep[u]<dep[v])swap(u,v);
  res+=query(1,id[v],id[u]);
  return res;    
}
void modify_tree(int u,int k){
  modify(1,id[u],id[u]+siz[u]-1,k);
}
ll query_tree(int u){
  return query(1,id[u],id[u]+siz[u]-1);
}
void solve(){
  cin>>n>>m>>r>>mod;
  for(int i=1;i<=n;i++)cin>>w[i];
  for(int i=1;i<n;i++){
      int u,v;
      cin>>u>>v;
      adj[u].push_back(v);
      adj[v].push_back(u);
  }
  dfs1(r,0);
  dfs2(r,r);
  build(1,1,n);
  while(m--){
      int op,x,y,z;
      cin>>op>>x;
      if(op==1){
          cin>>y>>z;
          modify_path(x,y,z);
      }
      else if(op==2){
          cin>>y;
          cout<<query_path(x,y)%mod<<"\n";
      }
      else if(op==3){
          cin>>z;
          modify_tree(x,z);
      }
      else{
          cout<<query_tree(x)%mod<<"\n";
      }
  }
}

    P2486 染色

题目描述

给定一棵 $n$ 个节点的无根树，共有 $m$ 个操作，操作分为两种：

  1. 将节点 $a$ 到节点 $b$ 的路径上的所有点（包括 $a$ 和 $b$）都染成颜色 $c$。
  2. 询问节点 $a$ 到节点 $b$ 的路径上的颜色段数量。

颜色段的定义是极长的连续相同颜色被认为是一段。例如 112221 由三段组成：11、222、1。

输入格式

输入的第一行是用空格隔开的两个整数，分别代表树的节点个数 $n$ 和操作个数 $m$。

第二行有 $n$ 个用空格隔开的整数，第 $i$ 个整数 $w_i$ 代表结点 $i$ 的初始颜色。

第 $3$ 到第 $(n + 1)$ 行，每行两个用空格隔开的整数 $u, v$，代表树上存在一条连结节点 $u$ 和节点 $v$ 的边。

第 $(n + 2)$ 到第 $(n + m + 1)$ 行，每行描述一个操作，其格式为：

每行首先有一个字符 $op$，代表本次操作的类型。

  • 若 $op$ 为 C，则代表本次操作是一次染色操作，在一个空格后有三个用空格隔开的整数 $a, b, c$，代表将 $a$ 到 $b$ 的路径上所有点都染成颜色 $c$。
  • 若 $op$ 为 Q，则代表本次操作是一次查询操作，在一个空格后有两个用空格隔开的整数 $a, b$，表示查询 $a$ 到 $b$ 路径上的颜色段数量。

输出格式

对于每次查询操作，输出一行一个整数代表答案。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
10
11
12

6 5
2 2 1 2 1 1
1 2
1 3
2 4
2 5
2 6
Q 3 5
C 2 1 1
Q 3 5
C 5 1 2
Q 3 5

样例输出 #1

1
2
3

3
1
2

提示

数据规模与约定

对于 $100\%$ 的数据，$1 \leq n, m \leq 10^5$，$1 \leq w_i, c \leq 10^9$，$1 \leq a, b, u, v \leq n$，$op$ 一定为 C 或 Q，保证给出的图是一棵树。

除原数据外，还存在一组不计分的 hack 数据。

思路

线段树维护信息，左颜色和右颜色，颜色总数，懒标记为是否涂色
难点：
这题重载运算符代替pushup方便后续计算
重链爬山法跳跃时，使用三个标记bool
g为0表示轮到L否则轮到R
lg表示L是否有跳跃过
rg表示R是否跳跃
定义线段的起始均为由深到浅，最后询问中间线段时，谁深度浅就翻转，判断合并即可

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

struct node{
    ll l,r,lc,rc,tag,sum;
    node operator+(const node&tmp){
        node ans;
        ans.l=l,ans.r=tmp.r;
        ans.lc=lc,ans.rc=tmp.rc;
        ans.sum=sum+tmp.sum-(rc==tmp.lc);
        ans.tag=0;
        return ans;
    }
} t[N<<2];
int w[N],siz[N],dep[N],par[N],son[N],top[N],id[N],nw[N],idx;
vector<int> adj[N];
void dfs1(int u,int fa){
    siz[u]=1;
    dep[u]=dep[fa]+1;
    par[u]=fa;
    for(auto v:adj[u]){
        if(v==fa)continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[son[u]]<siz[v])son[u]=v;
    }
}
void dfs2(int u,int t){
    top[u]=t;
    id[u]=++idx;
    nw[idx]=w[u];
    if(!son[u])return;
    dfs2(son[u],t);
    for(auto v:adj[u]){
        if(v==par[u]||v==son[u])continue;
        dfs2(v,v);
    }
}
void pushup(int p){
    t[p]=t[p<<1]+t[p<<1|1];
}
void pushdown(int p){
    auto &u=t[p],&l=t[p<<1],&r=t[p<<1|1];
    if(u.tag){
        l.sum=r.sum=1;
        l.lc=l.rc=r.lc=r.rc=l.tag=r.tag=u.tag;
        u.tag=0;
    }
}
void build(int p,int l,int r){
    t[p]={l,r,nw[l],nw[r],0,1};
    if(l==r)return;
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    pushup(p);
}
void modify(int p,int l,int r,int k){
    if(l<=t[p].l&&r>=t[p].r){
        t[p].tag=t[p].lc=t[p].rc=k;
        t[p].sum=1;
        return;
    }
    pushdown(p);
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid)modify(p<<1,l,r,k);
    if(r>mid)modify(p<<1|1,l,r,k);
    pushup(p);
}
node query(int p,int l,int r){
    if(l<=t[p].l&&r>=t[p].r)return t[p];
    pushdown(p);
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid&&r>mid)return query(p<<1,l,r)+query(p<<1|1,l,r);
    if(l<=mid)return query(p<<1,l,r);
    if(r>mid)return query(p<<1|1,l,r);
}
void modify_path(int u,int v,int k){//不做改变
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        modify(1,id[top[u]],id[u],k);
        u=par[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    modify(1,id[v],id[u],k);
}
node query_path(int u,int v){
    node L,R;
    int g=0,lg=0,rg=0;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v),g^=1;
        node res=query(1,id[top[u]],id[u]);
        if(res.r!=id[top[u]])swap(res.l,res.r),swap(res.lc,res.rc);
        u=par[top[u]];
        if(!g){
            if(!lg)L=res,lg=1;
            else L=L+res;
        }
        else{
            if(!rg)R=res,rg=1;
            else R=R+res;
        }
    }
    if(dep[u]<dep[v])swap(u,v),g^=1;
    node res=query(1,id[v],id[u]);
    if(!g){
        swap(L.lc,L.rc);
        if(lg&&rg)return R+res+L;
        if(lg)return res+L;
        if(rg)return R+res;
        return res;
    }
    swap(R.lc,R.rc);
    if(lg&&rg)return L+res+R;
    if(lg)return L+res;
    if(rg)return res+R;
    return res;
}
/*void modify_tree(int u,int k){
    modify(1,id[u],id[u]+siz[u]-1,k);
}
node query_tree(int u){
    return query(1,id[u],id[u]+siz[u]-1);
}*/
void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>w[i];
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs1(1,0);
    dfs2(1,1);
    build(1,1,n);
    while(m--){
        char op;
        cin>>op;
        int x,y,z;
        if(op=='C'){
            cin>>x>>y>>z;
            modify_path(x,y,z);
        }
        else{
            cin>>x>>y;
            cout<<query_path(x,y).sum<<"\n";
        }
    }
}

[国家集训队] 旅游(边权转点权)

题目背景

Ray 乐忠于旅游，这次他来到了 T 城。T 城是一个水上城市，一共有 $n$ 个景点，有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本，T 城的任意两个景点之间有且只有一条路径。换句话说， T 城中只有 $n-1$ 座桥。

Ray 发现，有些桥上可以看到美丽的景色，让人心情愉悦，但有些桥狭窄泥泞，令人烦躁。于是，他给每座桥定义一个愉悦度 $w$，也就是说，Ray 经过这座桥会增加 $w$ 的愉悦度，这或许是正的也可能是负的。有时，Ray 看待同一座桥的心情也会发生改变。

现在，Ray 想让你帮他计算从 $u$ 景点到 $v$ 景点能获得的总愉悦度。有时，他还想知道某段路上最美丽的桥所提供的最大愉悦度，或是某段路上最糟糕的一座桥提供的最低愉悦度。

题目描述

给定一棵 $n$ 个节点的树，边带权，编号 $0 \sim n-1$，需要支持五种操作：

  • C i w 将输入的第 $i$ 条边权值改为 $w$；
  • N u v 将 $u,v$ 节点之间的边权都变为相反数；
  • SUM u v 询问 $u,v$ 节点之间边权和；
  • MAX u v 询问 $u,v$ 节点之间边权最大值；
  • MIN u v 询问 $u,v$ 节点之间边权最小值。

保证任意时刻所有边的权值都在 $[-1000,1000]$ 内。

输入格式

第一行一个正整数 $n$，表示节点个数。
接下来 $n-1$ 行，每行三个整数 $u,v,w$，表示 $u,v$ 之间有一条权值为 $w$ 的边，描述这棵树。
然后一行一个正整数 $m$，表示操作数。
接下来 $m$ 行，每行表示一个操作。

输出格式

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

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
10
11
12

3
0 1 1
1 2 2
8
SUM 0 2
MAX 0 2
N 0 1
SUM 0 2
MIN 0 2
C 1 3
SUM 0 2
MAX 0 2

样例输出 #1

1
2
3
4
5
6

3
2
1
-1
5
3

提示

【数据范围】

对于 $100\%$ 的数据，$1\le n,m \le 2\times 10^5$。

2020.02.04 修正了一点数据的错误
2020.03.14 加入了一组 hack 数据
2020.11.26 加入了一组 hack 数据 By @_Leaving

思路

dfs序边权转点权，儿子记录边权信息
路径查询和修改时，上节点为原上节点的子节点(特别地，u==v不用计算)
修改单条边时，修改深度较深的点权
维护相反数：sum,mx,mn取反,swap(mx,mn)

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189

struct node{
    ll l,r,add,sum,mx,mn;
} t[N<<2];
ll w[N],siz[N],id[N],nw[N],dep[N],top[N],par[N],son[N];
vector<PII> adj[N];
void dfs1(int u,int fa){//预处理
    par[u]=fa;
    dep[u]=dep[fa]+1;
    siz[u]=1;
    for(auto [v,c]:adj[u]){
        if(v==fa)continue;
        w[v]=c;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[son[u]]<siz[v])son[u]=v;
    }
}
int cnt=0;
void dfs2(int u,int t){//dfs序，重链头节点
    id[u]=++cnt;
    nw[cnt]=w[u];
    top[u]=t;
    if(!son[u])return;
    dfs2(son[u],t);
    for(auto [v,c]:adj[u]){
        if(v==par[u]||v==son[u])continue;
        dfs2(v,v);
    }
}
void pushup(int p){
    t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
    t[p].mx=max(t[p<<1].mx,t[p<<1|1].mx);
    t[p].mn=min(t[p<<1].mn,t[p<<1|1].mn);
}
void pushdown(int p){
    auto &u=t[p],&l=t[p<<1],&r=t[p<<1|1];
    if(u.add){
        l.sum=-l.sum;
        r.sum=-r.sum;
        l.add^=1;
        r.add^=1;
        l.mx=-l.mx,l.mn=-l.mn,swap(l.mx,l.mn);
        r.mx=-r.mx,r.mn=-r.mn,swap(r.mx,r.mn);
        u.add=0;
    }
}
void build(int p,int l,int r){
    t[p]={l,r,0,nw[r],nw[r],nw[r]};
    if(l==r)return;
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    pushup(p);
}
void modify(int p,int x,int k){
    if(t[p].l==t[p].r){
        t[p].sum=t[p].mx=t[p].mn=k;
        t[p].add=0;
        return;
    }
    pushdown(p);
    int mid=t[p].l+t[p].r>>1;
    if(x<=mid)modify(p<<1,x,k);
    if(x>mid)modify(p<<1|1,x,k);
    pushup(p);   
}
void modify_rev(int p,int l,int r){
    if(l<=t[p].l&&r>=t[p].r){
        t[p].sum=-t[p].sum;
        t[p].mx=-t[p].mx;
        t[p].mn=-t[p].mn;
        swap(t[p].mx,t[p].mn);
        t[p].add^=1;
        return;
    }
    pushdown(p);
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid)modify_rev(p<<1,l,r);
    if(r>mid)modify_rev(p<<1|1,l,r);
    pushup(p);
}
ll query(int p,int l,int r){
    if(l<=t[p].l&&r>=t[p].r)return t[p].sum;
    pushdown(p);
    ll res=0;
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid)res+=query(p<<1,l,r);
    if(r>mid)res+=query(p<<1|1,l,r);
    return res;
}
ll query_mx(int p,int l,int r){
    if(l<=t[p].l&&r>=t[p].r)return t[p].mx;
    pushdown(p);
    ll res=-INF;
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid)res=max(res,query_mx(p<<1,l,r));
    if(r>mid)res=max(res,query_mx(p<<1|1,l,r));
    return res;
}
ll query_mn(int p,int l,int r){
    if(l<=t[p].l&&r>=t[p].r)return t[p].mn;
    pushdown(p);
    ll res=INF;
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid)res=min(res,query_mn(p<<1,l,r));
    if(r>mid)res=min(res,query_mn(p<<1|1,l,r));
    return res;
}
void modify_path(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        modify_rev(1,id[top[u]],id[u]);
        u=par[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    if(u!=v)modify_rev(1,id[v]+1,id[u]);
}
ll query_path(int u,int v){
    ll res=0;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        res+=query(1,id[top[u]],id[u]);
        u=par[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    if(u!=v)res+=query(1,id[v]+1,id[u]);
    return res;    
}
ll query_path_mx(int u,int v){
    ll res=-INF;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        res=max(res,query_mx(1,id[top[u]],id[u]));
        u=par[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    if(u!=v)res=max(res,query_mx(1,id[v]+1,id[u]));
    return res;    
}
ll query_path_mn(int u,int v){
    ll res=INF;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        res=min(res,query_mn(1,id[top[u]],id[u]));
        u=par[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    if(u!=v)res=min(res,query_mn(1,id[v]+1,id[u]));
    return res;    
}
struct edge{
    int u,v,c;
};
void solve(){
    int n;
    cin>>n;
    vector<edge> a(n+1);
    for(int i=1;i<n;i++){
        auto &[u,v,c]=a[i];
        cin>>u>>v>>c;
        u++;v++;
        adj[u].push_back({v,c});
        adj[v].push_back({u,c});
    }
    dfs1(1,0);
    dfs2(1,1);
    build(1,1,n);
    int q;
    cin>>q;
    //cout<<query_path(1,3)<<"\n";
    while(q--){
        string op;
        int x,y;
        cin>>op>>x>>y;
        x++;y++;
        if(op=="SUM")cout<<query_path(x,y)<<"\n";
        else if(op=="MAX")cout<<query_path_mx(x,y)<<"\n";
        else if(op=="MIN")cout<<query_path_mn(x,y)<<"\n";
        else if(op=="C"){
            x--;y--;
            auto [u,v,c]=a[x];
            if(dep[u]<dep[v])modify(1,id[v],y);
            else modify(1,id[u],y);
        }
        else{
            modify_path(x,y);
        }
    }
}

最短距离（基环树树剖）

题目描述

给出一个 $n$ 个点 $n$ 条边的无向连通图。

你需要支持两种操作：

  1. 修改 第 $x$ 条边的长度为 $y$ ；

  2. 查询 点 $x$ 到点 $y$ 的最短距离。

共有 $m$ 次操作。

输入格式

输入共 $n+m+1$ 行：

第 $1$ 行，包含两个正整数 $n,m$，表示点数即边数，操作次数。

第 $2$ 行到第 $n+1$ 行，每行包含三个正整数 $x,y,z$，表示 $x$ 与 $y$ 间有一条长度为 $z$ 的边。

第 $n+2$ 到 $n+m+1$ 行，每行包含三个正整数 $op,x,y$，表示操作种类，操作的参数（含义见【题目描述】）。

输出格式

对于每次操作 $2$ 输出查询的结果。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
10

4 5
1 2 11
1 3 12
2 3 13
1 4 15
2 2 3
1 2 1
2 2 3
2 2 4
2 3 4

样例输出 #1

1
2
3
4

13
12
26
16

提示

Luogu

对于 $100\%$ 的数据，保证 $z\in [0,5000]$。

思路

  • 利用并查集将多余的一条边挑出来，剩下n-1条边连边
  • 查询时，取以下三个值的最小值
    • $ dis(x,y) $
    • $ dis(x,u)+w+dis(v,y) $
    • $ dis(x,v)+w+dis(u,y) $
      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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

      struct node{
  int l,r,sum;
} t[N<<2];
vector<PII> adj[N];
int siz[N],son[N],par[N],dep[N],top[N],w[N],nw[N],id[N];
void dfs1(int u,int fa){
  dep[u]=dep[fa]+1;
  par[u]=fa;
  siz[u]=1;
  for(auto [v,c]:adj[u]){
  if(v==fa)continue;
  w[v]=c;
  dfs1(v,u);
  siz[u]+=siz[v];
  if(siz[son[u]]<siz[v])son[u]=v;
  }
}
int idx=0;
void dfs2(int u,int t){
  id[u]=++idx;
  nw[idx]=w[u];
  top[u]=t;
  if(!son[u])return;
  dfs2(son[u],t);
  for(auto [v,c]:adj[u]){
  if(v==par[u]||v==son[u])continue;
  dfs2(v,v);
  }
}
void pushup(int p){
  t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
void build(int p,int l,int r){
  t[p]={l,r,nw[r]};
  if(l==r)return;
  int mid=l+r>>1;
  build(p<<1,l,mid);
  build(p<<1|1,mid+1,r);
  pushup(p);
}
void modify_change(int p,int l,int r,int k){
  if(l<=t[p].l&&r>=t[p].r){
  t[p].sum=k;
  return;
  }
  //pushdown(p);
  int mid=t[p].l+t[p].r>>1;
  if(l<=mid)modify_change(p<<1,l,r,k);
  if(r>mid)modify_change(p<<1|1,l,r,k);
  pushup(p);
}
ll query(int p,int l,int r){
  if(l<=t[p].l&&r>=t[p].r)return t[p].sum;
  //pushdown(p);
  int mid=t[p].l+t[p].r>>1;
  ll res=0;
  if(l<=mid)res+=query(p<<1,l,r);
  if(r>mid)res+=query(p<<1|1,l,r);
  return res;
}
ll query_path(int u,int v){
  ll res=0;
  while(top[u]!=top[v]){
  if(dep[top[u]]<dep[top[v]])swap(u,v);
  res+=query(1,id[top[u]],id[u]);
  u=par[top[u]];
  }
  if(dep[u]<dep[v])swap(u,v);
  if(u!=v)res+=query(1,id[v]+1,id[u]);
  return res;
}
struct edge{
  int u,v,c;
};
int Set[N];
int find(int x){
  return Set[x]==x?x:Set[x]=find(Set[x]);
}
void solve(){
  int n,m;
  cin>>n>>m;
  vector<edge> e(n+1);
  int pos;
  for(int i=1;i<=n;i++)Set[i]=i;
  for(int i=1;i<=n;i++){
  auto &[u,v,c]=e[i];
  cin>>u>>v>>c;
  int fu=find(u),fv=find(v);
  if(fu==fv){
      pos=i;
      continue;
  }
  Set[fu]=fv;
  adj[u].push_back({v,c});
  adj[v].push_back({u,c});
  }
  dfs1(1,0);
  dfs2(1,1);
  build(1,1,n);
  while(m--){
  int op,x,y;
  cin>>op>>x>>y;
  if(op==1){
      if(x==pos)e[x].c=y;
      else{
          auto [u,v,c]=e[x];
          if(id[u]<id[v])modify_change(1,id[v],id[v],y);
          else modify_change(1,id[u],id[u],y);
      }
  }
  else{
      ll dis1=query_path(x,y);
      auto [u,v,c]=e[pos];
      ll dis2=query_path(x,u)+query_path(v,y)+c;
      ll dis3=query_path(x,v)+query_path(u,y)+c;
      cout<<min({dis1,dis2,dis3})<<"\n";
  }
  }
}

      [LNOI2014] LCA(差分+树剖)

题目描述

给出一个 $n$ 个节点的有根树（编号为 $0$ 到 $n-1$，根节点为 $0$）。

一个点的深度定义为这个节点到根的距离 $+1$。

设 $dep[i]$ 表示点 $i$ 的深度，$\operatorname{LCA}(i, j)$ 表示 $i$ 与 $j$ 的最近公共祖先。

有 $m$ 次询问，每次询问给出 $l, r, z$，求 $\sum_{i=l}^r dep[\operatorname{LCA}(i,z)]$ 。

输入格式

第一行 $2$ 个整数，$n, m$。

接下来 $n-1$ 行，分别表示点 $1$ 到点 $n-1$ 的父节点编号。

接下来 $m$ 行，每行 $3$ 个整数，$l, r, z$。

输出格式

输出 $q$ 行，每行表示一个询问的答案。每个答案对 $201314$ 取模输出。

样例 #1

样例输入 #1

1
2
3
4
5
6
7

5 2
0
0
1
1
1 4 3
1 4 2

样例输出 #1

1
2

8
5

提示

对于 $20\%$ 的数据，$n\le 10000,m\le 10000$；

对于 $40\%$ 的数据，$n\le 20000,m\le 20000$；

对于 $60\%$ 的数据，$n\le 30000,m\le 30000$；

对于 $80\%$ 的数据，$n\le 40000,m\le 40000$；

对于 $100\%$ 的数据，$1\le n\le 50000,1\le m\le 50000$。

思路

  • $ 每个询问[l,r]可以分解为[1,r]-[1,l-1] $
  • 深度可以看成节点到根的路径加1,预处理出来所有的节点,询问lca(i,z)即求1-z路径和
  • 为了防止计算 $ [l,r] $ 外的点,将l,r分别存储起来排序，然后可以从小到大添加i到节点的路径,单独计算单个点和z的答案,在最后再相减
    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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

    struct node{
  int l,r,add,sum;
} t[N<<2];
vector<int> adj[N];
int siz[N],son[N],par[N],dep[N],top[N],w[N],nw[N],id[N];
void dfs1(int u,int fa){
  dep[u]=dep[fa]+1;
  par[u]=fa;
  siz[u]=1;
  for(auto v:adj[u]){
      if(v==fa)continue;
      dfs1(v,u);
      siz[u]+=siz[v];
      if(siz[son[u]]<siz[v])son[u]=v;
  }
}
int idx=0;
void dfs2(int u,int t){
  id[u]=++idx;
  nw[idx]=w[u];
  top[u]=t;
  if(!son[u])return;
  dfs2(son[u],t);
  for(auto v:adj[u]){
      if(v==par[u]||v==son[u])continue;
      dfs2(v,v);
  }
}
void pushup(int p){
  t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
void pushdown(int p){
  auto &u=t[p],&l=t[p<<1],&r=t[p<<1|1];
  if(u.add){
      l.sum+=u.add*(l.r-l.l+1);
      r.sum+=u.add*(r.r-r.l+1);
      l.add+=u.add;
      r.add+=u.add;
      u.add=0;
  }
}
void build(int p,int l,int r){
  t[p]={l,r,0,nw[r]};
  if(l==r)return;
  int mid=l+r>>1;
  build(p<<1,l,mid);
  build(p<<1|1,mid+1,r);
  pushup(p);
}
void modify(int p,int l,int r,int k){
  if(l<=t[p].l&&r>=t[p].r){
      t[p].sum+=k*(t[p].r-t[p].l+1);
      t[p].add+=k;
      return;
  }
  pushdown(p);
  int mid=t[p].l+t[p].r>>1;
  if(l<=mid)modify(p<<1,l,r,k);
  if(r>mid)modify(p<<1|1,l,r,k);
  pushup(p);
}
ll query(int p,int l,int r){
  if(l<=t[p].l&&r>=t[p].r)return t[p].sum;
  pushdown(p);
  int mid=t[p].l+t[p].r>>1;
  ll res=0;
  if(l<=mid)res+=query(p<<1,l,r);
  if(r>mid)res+=query(p<<1|1,l,r);
  return res;
}
void modify_path(int u,int v,int k){
  while(top[u]!=top[v]){
      if(dep[top[u]]<dep[top[v]])swap(u,v);
      modify(1,id[top[u]],id[u],k);
      u=par[top[u]];
  }
  if(dep[u]<dep[v])swap(u,v);
  modify(1,id[v],id[u],k);
}
ll query_path(int u,int v){
  ll res=0;
  while(top[u]!=top[v]){
      if(dep[top[u]]<dep[top[v]])swap(u,v);
      res+=query(1,id[top[u]],id[u]);
      u=par[top[u]];
  }
  if(dep[u]<dep[v])swap(u,v);
  res+=query(1,id[v],id[u]);
  return res;
}
struct Q{
  int r,z,id;
  bool flag;
  bool operator<(const Q&tmp)const{
      return r<tmp.r;
  }
};
void solve(){
  int n,m;
  cin>>n>>m;
  for(int i=2;i<=n;i++){
      int u;
      cin>>u;
      u++;
      adj[u].push_back(i);
      adj[i].push_back(u);
  }
  dfs1(1,0);
  dfs2(1,1);
  build(1,1,n);
  vector<Q> q;
  vector<int> ans(m);
  for(int i=0;i<m;i++){
      int l,r,z;
      cin>>l>>r>>z;
      r++;z++;
      q.push_back({l,z,i,0});
      q.push_back({r,z,i,1});
  }
  sort(q.begin(),q.end());
  int R=0;
  for(int i=0;i<q.size();i++){
      auto [r,z,id,flag]=q[i];
      for(int j=R+1;j<=r;j++)modify_path(1,j,1);
      R=r;
      ans[id]+=(flag?1:-1)*query_path(1,z);
  }
  for(auto it:ans)cout<<it%mod<<"\n";
}

    长链剖分

    CF1009 Dominant Indices(模板)

    题意

    给定一棵树,对于每个点找出一个距离k,使得在该子树下与该点距离为k的点数最多

    思路

  • f[u][i]表示u节点距离为i的点数, $ f_{u,i}= \sum f_{v,i-1} $
  • 直接转移为 $ O(n^2) $

考虑优化,长链剖分,类似于启发式合并,定义深度最大的点为son[u]

  • 对于一条长链上的点使用同一块内存空间f[son[u]]=f[u]+1即向右移一次(假设u的第二维的头为1,向右移一位son[u]的第二维的头变成2,因此更新f[son[u]][i]即为更新f[u][i+1])
  • 除重儿子外的轻儿子,暴力转移(转移次数为dep[v]),总深度为n因此总复杂度为$ O(n) $
    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

    int dep[N],son[N],ans[N];
int buf[N],*f[N],*it=buf;
vector<int> adj[N];
void dfs1(int u,int fa){
  for(auto v:adj[u]){
      if(v==fa)continue;
      dfs1(v,u);
      if(dep[son[u]]<dep[v])son[u]=v;
  }
  dep[u]=dep[son[u]]+1;
}
void dfs2(int u,int fa){
  f[u][0]=1;
  if(!son[u])return;
  f[son[u]]=f[u]+1;
  dfs2(son[u],u);
  ans[u]=ans[son[u]]+1;
  if(f[u][ans[u]]==1)ans[u]=0;
  for(auto v:adj[u]){
      if(v==fa||v==son[u])continue;
      f[v]=it,it+=dep[v];
      dfs2(v,u);
      for(int i=1;i<=dep[v];i++){
          f[u][i]+=f[v][i-1];
          if(f[u][i]>f[u][ans[u]]||(f[u][i]==f[u][ans[u]]&&i<ans[u]))ans[u]=i;
      }
  }
}
void solve(){
  int n;
  cin>>n;
  for(int i=1;i<n;i++){
      int u,v;
      cin>>u>>v;
      adj[u].push_back(v);
      adj[v].push_back(u);
  }
  dfs1(1,0);
  f[1]=it,it+=dep[1];
  dfs2(1,0);
  for(int i=1;i<=n;i++)cout<<ans[i]<<"\n";
}

    P3565 [POI2014] HOT-Hotels(长链剖分+树形dp)

    题意：
    给定一棵树，在树上选3个点，要求两两距离相等，求方案数。 思路：

  • $ 定义f_{u,i}表示以u为根的子树，与点u距离为i的点数 $
  • $ 定义g_{u,i}表示以u为根的子树，满足以下条件的点对数 $
    • $ 设点对(x,y)，他们到lca(x,y)的距离为d，lca(x,y)到点u的距离为d-i $
  • 更新答案
    • 在之前的分支选择两个点，在当前分支选择一个点
      $ ans+=g_{u,i+1} \times f_{v,i} $
    • 在之前分支选一个点，在当前分支选两个点
      $ ans+=f_{u,i-1} \times g_{v,i}$
  • 更新f数组
    • $ f_{u,i+1}+=f_{v,i} $
  • 更新g数组
    • $ g_{u,i-1}+=g_{v,i} $
    • $ g_{u,i+1}+=f_{u,i+1} \times f_{v,i} (此时d的值为d=i+1)$
  • 注意事项：采用指针赋值，g数组传给重儿子时指针是向前移的，这样就可能会遍历到不是当前领域的数，因此赋值需要给每条长链两倍空间
    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

    vector<int> adj[N];
ll buf[N<<2];
ll dep[N],son[N],*f[N],*g[N],*id=buf;
void dfs1(int u,int fa){
  for(auto v:adj[u]){
      if(v==fa)continue;
      dfs1(v,u);
      if(dep[v]>dep[son[u]])son[u]=v;
  }
  dep[u]=dep[son[u]]+1;
}
ll ans;
void dfs2(int u,int fa){
  if(son[u]){
      f[son[u]]=f[u]+1;
      g[son[u]]=g[u]-1;
      dfs2(son[u],u);
  }
  f[u][0]=1;
  ans+=g[u][0];
  for(auto v:adj[u]){
      if(v==fa||v==son[u])continue;
      f[v]=id,id+=dep[v]+10;
      g[v]=id,id+=dep[v]+10;
      dfs2(v,u);
      for(int i=0;i<dep[v];i++){
          if(i)ans+=f[u][i-1]*g[v][i];
          ans+=g[u][i+1]*f[v][i];
      }
      for(int i=0;i<dep[v];i++){
          g[u][i+1]+=f[u][i+1]*f[v][i];
          if(i)g[u][i-1]+=g[v][i];
          f[u][i+1]+=f[v][i];
      }
  }
}
void solve(){
  int n;
  cin>>n;
  for(int i=1;i<n;i++){
      int u,v;
      cin>>u>>v;
      adj[u].push_back(v);
      adj[v].push_back(u);
  }
  dfs1(1,0);
  f[1]=id,id+=dep[1]+10;
  g[1]=id,id+=dep[1]+10;
  dfs2(1,0);
  cout<<ans<<"\n";
}
树链剖分
算法 树
This post is licensed under CC BY 4.0 by the author.