[SDOI 2014]旅行题解 树链剖分 动态开点

题目：https://www.luogu.org/problemnew/show/P3313

做前须知：树链剖分（我的博客：https://blog.csdn.net/weixin_43790474/article/details/84556647 ）
线段树动态开点（我这方面写得不太好，可以去找别的大佬的看看，建议看看主席树）。
首先，看题干，这道题大致要支持如下几个操作：
1.修改点的类型（城市所属宗教）
2.修改点的权值（城市对应评级）
3.一条路径上与出发点同类型的权值和
4.一条路径上与出发点同类型的最大权值
首先，看操作3、4，树上对路径操作，还带修改，树链剖分没得跑（当然，我不会lct，我太蒻了）。但是，我们发现，简单的树剖是行不通的，因为它还要求只能计算与出发点类型相同的节点。那么，有没有什么办法，能够让我们无论是修改还是查询，都只对相同类型的点进行操作呢？
显然是有的，我们完全可以对每一个类型都建一棵线段树，再用树剖维护嘛，这样，无论是查询还是修改我们都可以做到只对同类型的点操作。但，新的问题出现了，n棵线段树，空间复杂度似乎太大了，没事，动态开点是个好东西（不会的自行百度）。那么，通过动态开点，我们对于每一个点，都只在线段树上增加了一条链，那么空间复杂度显然是(nlogn)，时间呢就是O(nlog²n)（树剖*线段树）了。这道题就解决了。（自己稍微注意一下，空间限制为128M，该剪枝的就要剪枝，不然全mle搞得你头皮发麻）附代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100010;
inline int read()
{
int res;
char ch;
while (!isdigit(ch = getchar()));
res = ch - '0';
while (isdigit(ch = getchar()))
{
res = res * 10 + ch - '0';
}
return res;
}
int n , q , tot , mv;
int v[maxn] , belong[maxn];
struct edge
{
int v , next;
}E[maxn * 2];
int len , head[maxn];
void add(int u , int v)
{
E[len].v = v , E[len].next = head[u];
head[u] = len++;
}
int son[maxn] , fa[maxn] , top[maxn] , sz[maxn] , dep[maxn] , tid[maxn];
void dfs1(int u)
{
sz[u] = 1;
for (int i = head[u]; ~i; i = E[i].next)
{
int v = E[i].v;
if (v != fa[u])
{
fa[v] = u;
dep[v] = dep[u] + 1;
dfs1(v);
sz[u] += sz[v];
if (son[u] == -1 || sz[v] > sz[son[u]])
{
son[u] = v;
}
}
}
}
void dfs2(int u , int Top)
{
top[u] = Top;
tid[u] = ++tot;
if (son[u] != -1)
{
dfs2(son[u] , Top);
}
for (int i = head[u]; ~i; i = E[i].next)
{
int v = E[i].v;
if (v != fa[u] && v != son[u])
{
dfs2(v , v);
}
}
}
int sum[maxn * 20] , maxv[maxn * 20] , ls[maxn * 20] , rs[maxn * 20] , rt[maxn];
void update(int &id , int l , int r , int pos , int val)
{
if (!id)
{
id = ++tot;
}
int mid = (l + r) >> 1;
sum[id] += val;
maxv[id] = max(maxv[id] , val);
if (l == r)
{
return;
}
if (pos <= mid)
{
update(ls[id] , l , mid , pos , val);
}
else
{
update(rs[id] , mid + 1 , r , pos , val);
}
}
void del(int id , int l , int r , int pos)
{
if (!id)
{
return;
}
if (l == r)
{
sum[id] = 0;
maxv[id] = 0;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid)
{
del(ls[id] , l , mid , pos);
}
else
{
del(rs[id] , mid + 1 , r , pos);
}
sum[id] = sum[ls[id]] + sum[rs[id]];
maxv[id] = max(maxv[ls[id]] , maxv[rs[id]]);
}
int query(int s , int l , int r , int x , int y , int judge)
{
if (!s)
{
return 0;
}
if (l >= x && r <= y)
{
if (judge)
{
return sum[s];
}
else
{
return maxv[s];
}
}
int mid = (l + r) >> 1;
int res = 0;
if (x <= mid)
{
if (judge)
{
res += query(ls[s] , l , mid , x , y , judge);
}
else
{
res = max(res , query(ls[s] , l , mid , x , y , judge));
}
}
if (y > mid)
{
if (judge)
{
res += query(rs[s] , mid + 1 , r , x , y , judge);
}
else
{
res = max(res , query(rs[s] , mid + 1 , r , x , y , judge));
}
}
return res;
}
int query_path(int x , int y , int judge)
{
int res = 0;
int aim = belong[x];
while (top[x] != top[y])
{
if (dep[top[x]] < dep[top[y]])
{
swap(x , y);
}
if (judge)
{
res += query(rt[aim] , 1 , mv , tid[top[x]] , tid[x] , judge);
}
else
{
res = max(res , query(rt[aim] , 1 , mv , tid[top[x]] , tid[x] , judge));
}
x = fa[top[x]];
}
if (dep[x] > dep[y])
{
swap(x , y);
}
if (judge)
{
res += query(rt[aim] , 1 , mv , tid[x] , tid[y] , judge);
}
else
{
res = max(res , query(rt[aim] , 1 , mv , tid[x] , tid[y] , judge));
}
return res;
}
int main()
{
memset(head , -1 , sizeof(head));
memset(son , -1 , sizeof(son));
n = read() , q = read();
for (int i = 1; i <= n; i++)
{
v[i] = read() , belong[i] = read();
}
mv = n;
for (int i = 1; i < n; i++)
{
int u , v;
u = read() , v = read();
add(u , v);
add(v , u);
}
dfs1(1);
dfs2(1 , 1);
tot = 0;
for (int i = 1; i <= n; i++)
{
update(rt[belong[i]] , 1 , mv , tid[i] , v[i]);
}
char op[5];
for (int i = 1; i <= q; i++)
{
scanf("%s" , &op);
int x , y , c , w;
if (op[0] == 'Q' && op[1] == 'S')
{
x = read() , y = read();
printf("%dn" , query_path(x , y , 1));
}
else if (op[0] == 'Q' && op[1] == 'M')
{
x = read() , y = read();
printf("%dn" , query_path(x , y , 0));
}
else if (op[0] == 'C' && op[1] == 'C')
{
x = read() , c = read();
del(rt[belong[x]] , 1 , mv , tid[x]);
belong[x] = c;
update(rt[c] , 1 , mv , tid[x] , v[x]);
}
else if (op[0] == 'C' && op[1] == 'W')
{
x = read() , w = read();
del(rt[belong[x]] , 1 , mv , tid[x]);
v[x] = w;
update(rt[belong[x]] , 1 , mv , tid[x] , w);
}
}
return 0;
}

最后

以上就是诚心春天为你收集整理的[SDOI 2014]旅行题解 树链剖分 动态开点的全部内容，希望文章能够帮你解决[SDOI 2014]旅行题解 树链剖分 动态开点所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。