树链剖分题集

树链剖分常用于处理静态树上操作，效率很高，写起来也就是固定的轻重边拆分+线段树，但是代码一般都是100行+，容易出错。
本题集中的树链剖分练习题，在解决思路上没什么难点，主要是如何设计线段树以及如何更新+询问，也就是说要想好怎么维护线段树，其它地方没什么太难的，但是代码长就容易出bug，多写写就好了。最后一题是线段树动态开点，这和可持久化权值线段树（动态主席树）一样的思想，只需要将普通的线段树给稍微修改一下即可。

树的统计

题意简述
原题来自：ZJOI 2008
一树上有 n 个节点，编号分别为 1 到 n，每个节点都有一个权值 w。我们将以下面的形式来要求你对这棵树完成一些操作：

1.CHANGE u t ：把节点 u 权值改为 t；

2.QMAX u v ：询问点 u 到点 v 路径上的节点的最大权值；

3.QSUM u v ：询问点 u 到点 v 路径上的节点的权值和。

注意：从点 u 到点 v 路径上的节点包括 u 和 v 本身。

解题思路
树链剖分+线段树上单点修改，区间查询，需要注意查询操作，利用到了LCA倍增思想，树链剖分中很多区间修改和查询操作都是这样完成的。

代码示例

#include
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int N = 3e4+10;
const int M = 2*N;
int head[N],ver[M],edge[M],nex[M],tot = 1;
void addEdge(int x,int y,int z){ver[++tot] = y, edge[tot] = z;nex[tot] = head[x], head[x] = tot;
}
int n,q,a[N];
/*父亲,深度,子树大小,重儿子,重路径顶部节点,树中节点在线段树中下标,线段树中节点对应树中位置*/
int par[N],deep[N],size[N],son[N],top[N],seg[N],rev[N];
int vis[N];
void dfs1(int x,int fa){/*利用深搜更新par,size,deep,son数组*/vis[x] = true; size[x] = 1;par[x] = fa; deep[x] = deep[fa]+1;for(int i = head[x];i ;i = nex[i]){int y = ver[i], z = edge[i];if(y == fa || vis[y]) continue;dfs1(y,x);size[x] += size[y]; //累加子树大小if(size[y] > size[son[x]]) son[x] = y;//求重儿子}
}
void dfs2(int x,int fa){if(son[x]){ //先走重儿子,使得重路径在线段树中连续seg[son[x]] = ++seg[0];//0位置用不到,利用来计数top[son[x]] = top[x];rev[seg[0]] = son[x];dfs2(son[x],x);}for(int i = head[x];i;i = nex[i]){int y = ver[i], z = edge[i];if(top[y]) continue;/*若y没有被遍历过,即y不是x的重儿子或者父亲*/seg[y] = ++seg[0]; rev[seg[0]] = y;top[y] = y; dfs2(y,x);/*如果x-->y是轻边,那么y就是其所在重路径顶部节点*/}
}
struct SegmentTree{int l,r;ll mx, sum;#define l(x) t[x].l#define r(x) t[x].r#define mx(x) t[x].mx#define sum(x) t[x].sum
}t[N*4];
void BuildTree(int rt,int l,int r){l(rt) = l, r(rt) = r;if(l == r){mx(rt) = sum(rt) = a[rev[l]]; //线段树上l节点对应着树上rev[l]点return;}int mid = l+r>>1;BuildTree(rt*2,l,mid); BuildTree(rt*2+1,mid+1,r);mx(rt) = max(mx(rt<<1),mx(rt<<1|1));sum(rt) = sum(rt<<1) + sum(rt<<1|1);
}
void preHandle(){dfs1(1,0); //我们以1号节点为根/*根节点所在重路径的顶部节点也是根节点,赋初值*/seg[0] = seg[1] = top[1] = rev[1] = 1;dfs2(1,0);BuildTree(1,1,seg[0]);
}
ll tmx,tsum;//利用全局变量同时统计2个答案
void query(int rt,int l,int r){/*将以rt为根的区间内属于[l,r]部分的和累加到tsum上,并更新tmx*/if(l <= l(rt) && r(rt) <= r){tsum += sum(rt); tmx = max(tmx,mx(rt));return ;}int mid = l(rt)+r(rt)>>1;if(l <= mid) query(rt<<1,l,r);if(r > mid) query(rt<<1|1,l,r);
}
void ask(int x,int y){/*返回x与y之间路径上权值最大点的权值*/int fx = top[x] , fy = top[y];while(fx != fy){//先将x和y条整到同一个重链上if(deep[fx] < deep[fy]) swap(x,y),swap(fx,fy);query(1,seg[fx],seg[x]);x = par[fx]; fx = top[x];}if(deep[x] > deep[y]) swap(x,y);//路径浅的编号小query(1,seg[x],seg[y]); //再更新一次
}
void change(int rt,int x,int val){/*把线段树节点x的权值改为val*/if(l(rt) == r(rt)){mx(rt) = sum(rt) = val;return;}int mid = l(rt) + r(rt) >> 1;if(x > mid) change(rt<<1|1,x,val);else change(rt<<1,x,val);mx(rt) = max(mx(rt<<1),mx(rt<<1|1));sum(rt) = sum(rt<<1) + sum(rt<<1|1);
}
int main(){#ifdef LOCALfreopen("123.txt","r",stdin);freopen("222.txt","w",stdout);#endifscanf("%d",&n);for(int i = 1,x,y;i < n;i++){scanf("%d%d",&x,&y);addEdge(x,y,1); addEdge(y,x,1);}for(int i = 1;i <= n;i++) scanf("%d",a+i);scanf("%d",&q);preHandle();//树链剖分预处理char op[20];for(int i = 1,x,y;i <= q;i++){scanf("%s%d%d",op,&x,&y);if(op[0] == 'C') change(1,seg[x],y);else{tmx = -INF; tsum = 0;ask(x,y);//同时更新最大值与路径和if(op[1] == 'M') printf("%lld\n",tmx);else printf("%lld\n",tsum);}}return 0;
}

「HAOI2015」树上操作

题意简述
有一棵点数为 N 的树，以点 1 为根，且树有点权。然后有 M 个操作，分为三种：

1、把某个节点 x 的点权增加 a 。

2、把某个节点 x 为根的子树中所有点的点权都增加 a 。

3、询问某个节点 x 到根的路径中所有点的点权和。

解题思路
树链剖分+线段树上区间修改，区间查询。用到了线段树上的延迟标记，其实和普通线段树没啥区别，就是查询和修改时候要用LCA倍增思想将树上的链转化为线段树上的区间。只要理解了树上节点和线段树下标是通过seg[x] 和 rev[seg[x]]来转换的即可。

另外还需要明白线段树上重链的seg[]值是连续的，同一个子树上的所有节点下标也是连续的，这个结论可以通过观察dfs2的实现得到。

代码示例

#include
using namespace std;
typedef long long ll;
const int N = 1e5+10;
const int M = 2e5+10;
int head[N],ver[M],edge[M],nex[M],tot = 1;
void addEdge(int x,int y,int z){ver[++tot] = y,edge[tot] = z;nex[tot] = head[x]; head[x] = tot;
}
int n,m,a[N];
int getInt() {int ans = 0;bool neg = false;char c = getchar();while (c!='-' && (c<'0' || c>'9')) c = getchar();if (c == '-') neg = true, c = getchar();while (c>='0' && c<='9')ans = ans*10 + c-'0', c = getchar();return neg ? -ans : ans; 
}
int deep[N],par[N],top[N],size[N],son[N],seg[N],rev[N];
int vis[N];
void dfs1(int x,int fa){vis[x] = true; par[x] = fa;deep[x] = deep[fa]+1; size[x] = 1;for(int i = head[x];i ;i = nex[i]){int y = ver[i], z = edge[i];if(vis[y] || y == fa) continue;dfs1(y,x);size[x] += size[y]; if(size[y] > size[son[x]]) son[x] = y;}
}
void dfs2(int x,int fa){if(son[x]){seg[son[x]] = ++seg[0];rev[seg[0]] = son[x];top[son[x]] = top[x];dfs2(son[x],x);}for(int i = head[x];i;i = nex[i]){int y = ver[i], z = edge[i];if(top[y]) continue;seg[y] = ++seg[0]; rev[seg[0]] = y;top[y] = y; dfs2(y,x);}
}
struct SegmentTree{int l,r;ll sum,add;#define l(x) t[x].l#define r(x) t[x].r#define sum(x) t[x].sum#define add(x) t[x].add
}t[N*4];
void BuildTree(int rt,int l,int r){l(rt) = l,r(rt) = r,add(rt) = 0;if(l == r){sum(rt) = a[rev[l]]; return;}int mid = l+r>>1;BuildTree(rt<<1,l,mid); BuildTree(rt<<1|1,mid+1,r);sum(rt) = sum(rt<<1) + sum(rt<<1|1);
}
void preHandle(){dfs1(1,0);seg[0] = seg[1] = top[1] = rev[1] = 1;dfs2(1,0);BuildTree(1,1,seg[0]);
}
void spread(int rt){if(!add(rt)) return;sum(rt<<1) += (r(rt<<1)-l(rt<<1)+1)*add(rt);sum(rt<<1|1) += (r(rt<<1|1)-l(rt<<1|1)+1)*add(rt);add(rt<<1) += add(rt); add(rt<<1|1) += add(rt);add(rt) = 0;
}
void Add(int rt,int l,int r,ll val){if(l <= l(rt) && r(rt) <= r){sum(rt) += (r(rt) - l(rt)+1)*val;add(rt) += val; return;}spread(rt);int mid = l(rt)+r(rt)>>1;if(l <= mid) Add(rt<<1,l,r,val);if(r > mid) Add(rt<<1|1,l,r,val);sum(rt) = sum(rt<<1)+sum(rt<<1|1);
}
ll query(int rt,int l,int r){if(l <= l(rt) && r(rt) <= r) return sum(rt);spread(rt); ll res = 0;int mid = l(rt) + r(rt) >> 1;if(l <= mid) res += query(rt<<1,l,r);if(r > mid) res += query(rt<<1|1,l,r);return res;
}
ll ask(int x){/*从节点x到根节点的路径和*/ll res = 0;while(x){res += query(1,seg[top[x]],seg[x]);x = par[top[x]];}return res;
}
int main(){n = getInt(); m = getInt();for(int i = 1;i <= n;i++) a[i] = getInt();for(int i = 1,x,y;i < n;i++){x = getInt(); y = getInt();addEdge(x,y,1); addEdge(y,x,1);}preHandle();for(int i = 1,op,x,y;i <= m;i++){op = getInt();if(op == 1){x = getInt(); y = getInt();Add(1,seg[x],seg[x],y);}else if(op == 2){x = getInt(); y = getInt();Add(1,seg[x],seg[x]+size[x]-1,y);}else{x = getInt(); printf("%lld\n",ask(x));}}return 0;
}

「NOI2015」软件包管理器

题意简述
Linux 用户和 OSX 用户一定对软件包管理器不会陌生。通过软件包管理器，你可以通过一行命令安装某一个软件包，然后软件包管理器会帮助你从软件源下载软件包，同时自动解决所有的依赖（即下载安装这个软件包的安装所依赖的其它软件包），完成所有的配置。Debian/Ubuntu 使用的 apt-get，Fedora/CentOS 使用的 yum，以及 OSX 下可用的 Homebrew 都是优秀的软件包管理器。

你决定设计你自己的软件包管理器。不可避免地，你要解决软件包之间的依赖问题。如果软件包 A 依赖软件包 B，那么安装软件包 A 以前，必须先安装软件包 B。同时，如果想要卸载软件包 B，则必须卸载软件包 A。现在你已经获得了所有的软件包之间的依赖关系。而且，由于你之前的工作，除 0 号软件包以外，在你的管理器当中的软件包都会依赖一个且仅一个软件包，而 0 号软件包不依赖任何一个软件包。依赖关系不存在环（若有m(m≥2) 个软件包A1,A2,A3,…,Am ，其中 A1 依赖 A2，A2依赖 A3 依赖 A4 ，……，Am−1 依赖 Am ，而 Am 依赖 A1 ，则称这 m 个软件包的依赖关系构成环），当然也不会有一个软件包依赖自己。

现在你要为你的软件包管理器写一个依赖解决程序。根据反馈，用户希望在安装和卸载某个软件包时，快速地知道这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包），你的任务就是实现这个部分。注意，安装一个已安装的软件包，或卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为 0。

解题思路
要画图理解题意，若A依赖B，则安装A之前要安装B，若卸载B要先卸载A。也就是说要安装A，就要确保A到根节点路径上软件都已安装；若卸载A，就要确保 A 的子树为空。

于是就是树上操作，若卸载一个软件 x ，就是查询它子树上已安装的软件个数（包括它自己），输出后再删除即可；若安装一个软件 x ，就是查询 x 到根节点路径上未安装的软件个数（包括它自己），输出后再安装。因为软件安装和卸载只是改变其状态（已安装：1，未安装：0），而不改变结构（彻底删除节点），所以可以用树链剖分+线段树解决。

但是需要注意的是，怎么把整棵子树都清零，怎么把到根节点的路径都置 1，显然要用延迟标记，但是延迟标记却不应该累加，那要怎么处理？
置 1 时延迟标记add = 1，置0时延迟标记add = -1，每一个节点如果延迟标记不为0，那么该节点为根的子树所有软件状态相同。我们下传延迟标记操作封装在spread函数内，可以参考如何实现延迟标记的更新。

代码示例

#include
using namespace std;
const int N = 1e5+10;
const int M = 2e5+10;
typedef int ll;
int head[N],ver[M],edge[M],nex[M],tot = 1;
void addEdge(int x,int y,int z){ver[++tot] = y, edge[tot] = z;nex[tot] = head[x], head[x] = tot;
}
int n,m;
int par[N],deep[N],size[N],son[N],top[N],seg[N],rev[N];
int vis[N];
void dfs1(int x,int fa){vis[x] = true; par[x] = fa;deep[x] = deep[fa]+1; size[x] = 1;for(int i = head[x];i ;i = nex[i]){int y = ver[i], z = edge[i];if(vis[y]) continue;dfs1(y,x);size[x] += size[y];if(size[y] > size[son[x]]) son[x] = y;}
}
void dfs2(int x,int fa){if(son[x]){seg[son[x]] = ++seg[0];rev[seg[0]] = son[x];top[son[x]] = top[x];dfs2(son[x],x);}for(int i = head[x];i ;i = nex[i]){int y = ver[i], z = edge[i];if(top[y]) continue;seg[y] = ++seg[0]; rev[seg[0]] = y;top[y] = y; dfs2(y,x);}
}
struct SegmentTree{int l,r,sum,add;#define l(x) t[x].l#define r(x) t[x].r#define sum(x) t[x].sum#define add(x) t[x].add
}t[N*4];
void BuildTree(int rt,int l,int r){l(rt) = l,r(rt) = r,add(rt) = sum(rt) = 0;if(l == r) return;int mid = l+r>>1;BuildTree(rt<<1,l,mid); BuildTree(rt<<1|1,mid+1,r);sum(rt) = sum(rt<<1) + sum(rt<<1|1);
}
void preHandle(){dfs1(1,0);seg[0] = seg[1] = top[1] = rev[1] = 1;dfs2(1,0);BuildTree(1,1,seg[0]);
}
void spread(int rt){if(!add(rt)) return; if(add(rt) == -1){sum(rt<<1) = sum(rt<<1|1) = 0;add(rt<<1) = add(rt<<1|1) = add(rt);add(rt) = 0; return;}sum(rt<<1) = (r(rt<<1)-l(rt<<1)+1)*add(rt);sum(rt<<1|1) = (r(rt<<1|1)-l(rt<<1|1)+1)*add(rt);add(rt<<1) = add(rt); add(rt<<1|1) = add(rt);add(rt) = 0;
}
void Add(int rt,int l,int r,ll val){if(l <= l(rt) && r(rt) <= r){if(val == -1) sum(rt) = 0;else sum(rt) = (r(rt) - l(rt)+1);add(rt) = val; return;}spread(rt);int mid = l(rt)+r(rt)>>1;if(l <= mid) Add(rt<<1,l,r,val);if(r > mid) Add(rt<<1|1,l,r,val);sum(rt) = sum(rt<<1)+sum(rt<<1|1);
}
ll query(int rt,int l,int r){if(l <= l(rt) && r(rt) <= r) return sum(rt);spread(rt); ll res = 0;int mid = l(rt) + r(rt) >> 1;if(l <= mid) res += query(rt<<1,l,r);if(r > mid) res += query(rt<<1|1,l,r);return res;
}
int ask1(int x){return query(1,seg[x],seg[x]+size[x]-1);
}
int ask2(int x){int res = 0;while(x){res += query(1,seg[top[x]],seg[x]);x = par[top[x]];}return res;
}
void Add2(int x){while(x){Add(1,seg[top[x]],seg[x],1);x = par[top[x]];}
}
int main(){scanf("%d",&n);for(int i = 1,x;i < n;i++){scanf("%d",&x);addEdge(x+1,i+1,1); addEdge(i+1,x+1,1);}preHandle();scanf("%d",&m); char op[22];for(int i = 1,x;i <= m;i++){scanf("%s%d",op,&x); x++;if(op[0] == 'u'){printf("%d\n",ask1(x));Add(1,seg[x],seg[x]+size[x]-1,-1);}else{printf("%d\n",deep[x]-ask2(x));Add2(x);}}return 0;
}

染色

题意简述
原题来自：SDOI 2011
给定一棵有 n 个节点的无根树和 m 个操作，操作共两类。
1、将节点 a 到节点 b 路径上的所有节点都染上颜色；
2、询问节点 a 到节点 b 路径上的颜色段数量，连续相同颜色的认为是同一段，例如 112221 由三段组成：11 、 222、1。

请你写一个程序依次完成操作。

解题思路
如果不是在树上，是在区间上，该如何操作？用线段树解决。线段树上每个节点有lc：左端点颜色，rc：右端点颜色，same：区间颜色是否唯一（1表示唯一，0表示不唯一），sum：区间内颜色段数量。
那么更新显然要用延迟标记，标记在same上，而合并操作需要考虑中间相接的端点颜色是否相同，若相同则颜色段数量要-1。于是区间上“染色”问题就可以用线段树解决了。

在树上显然类似，因为我们可以通过树链剖分来将树给转化为区间。唯一麻烦的地方就是端点颜色问题，在区间上，我们只需要判断左子树的右端点、右子树的左端点是否颜色相同即可，但是树上的路径是通过倍增来找的，显然需要记录每一条链的端点颜色，麻烦在于如何记录并判断。

树链剖分后节点越浅，其seg越小，于是需要判断颜色是否相同的是seg[fx]和 seg[par[fx]]，这是由于我们在倍增调整深度时候是自底向上的，自然要判断深度浅的节点。为了美观以及简便，设 getcol(x) 返回该节点的颜色。

代码示例

#include
using namespace std;
const int N = 1e5+10;
const int M = 2e5+10;
const int INF = 0x3f3f3f3f;
int head[N],edge[M],ver[M],nex[M], tot = 1;
void addEdge(int x,int y,int z){ver[++tot] = y, edge[tot] = z;nex[tot] = head[x], head[x] = tot;
}
int deep[N],seg[N],rev[N],top[N],son[N],size[N],par[N];
int vis[N],a[N];
void dfs1(int x,int fa){vis[x] = true; par[x] = fa;deep[x] = deep[fa]+1; size[x] = 1;for(int i = head[x];i;i = nex[i]){int y = ver[i], z = edge[i];if(vis[y] || y == fa) continue;dfs1(y,x);size[x] += size[y];if(size[y] > size[son[x]]) son[x] = y;}
}
void dfs2(int x,int fa){if(son[x]){seg[son[x]] = ++seg[0];rev[seg[0]] = son[x];top[son[x]] = top[x];dfs2(son[x],x);}for(int i = head[x];i;i = nex[i]){int y = ver[i], z = edge[i];if(top[y]) continue;seg[y] = ++seg[0]; rev[seg[0]] = y;top[y] = y; dfs2(y,x);}
}
struct SegmentTree{/*lc:区间左端点颜色,rc:区间右端点颜色,sum:区间内颜色段数*/int l,r,lc,rc,sum;int same;#define l(x) t[x].l#define r(x) t[x].r#define lc(x) t[x].lc#define rc(x) t[x].rc#define sum(x) t[x].sum#define same(x) t[x].same
}t[N*4];
void Updata(int rt){//更新节点rt的same、rc、lc和sumsame(rt) = same(rt<<1) && same(rt<<1|1) && rc(rt<<1) == lc(rt<<1|1);sum(rt) = sum(rt<<1)+sum(rt<<1|1);if(rc(rt<<1) == lc(rt<<1|1)) sum(rt)--;lc(rt) = lc(rt<<1); rc(rt) = rc(rt<<1|1);
}
void BuildTree(int rt,int l,int r){l(rt) = l,r(rt) = r,same(rt) = 0;if(l == r){lc(rt) = rc(rt) = a[rev[l]];sum(rt) = 1; return;}int mid = l + r >> 1;BuildTree(rt<<1,l,mid); BuildTree(rt<<1|1,mid+1,r);Updata(rt);
}
void preHandle(){dfs1(1,0);seg[0] = seg[1] = rev[1] = top[1] = 1;dfs2(1,0);BuildTree(1,1,seg[0]);
}
void spread(int rt){if(!same(rt)) return;//将懒惰标记下传，即对子树染相同颜色sum(rt<<1) = sum(rt<<1|1) = 1;lc(rt<<1) = rc(rt<<1) = lc(rt<<1|1) = rc(rt<<1|1) = lc(rt);same(rt<<1) = same(rt<<1|1) = 1; same(rt) = 0;
}
void modify(int rt,int l,int r,int col){if(l <= l(rt) && r(rt) <= r){sum(rt) = 1; lc(rt) = rc(rt) = col;same(rt) = 1; return;}spread(rt);//懒惰标记int mid = l(rt)+r(rt)>>1;if(l <= mid) modify(rt<<1,l,r,col);if(r > mid) modify(rt<<1|1,l,r,col);Updata(rt);
}
void change(int x,int y,int z){int fx = top[x],fy = top[y];while(fx != fy){if(deep[fx] < deep[fy]) swap(x,y),swap(fx,fy);modify(1,seg[fx],seg[x],z);x = par[fx]; fx = top[x];}if(deep[x] > deep[y]) swap(x,y);modify(1,seg[x],seg[y],z);
}
int query(int rt,int l,int r){if(l <= l(rt) && r(rt) <= r) return sum(rt);spread(rt);int mid = l(rt)+r(rt)>>1 ,res= 0;if(l <= mid) res += query(rt<<1,l,r);if(r > mid) res += query(rt<<1|1,l,r);/*合并时中间颜色相同,要减去一段*/if(l <= mid && mid < r && rc(rt<<1) == lc(rt<<1|1)) res--;return res;
}
int getcol(int rt,int x){//这个函数太好用了，哭哭if(l(rt) == r(rt)) return lc(rt);spread(rt);int mid = l(rt)+r(rt)>>1;if(x <= mid) return getcol(rt<<1,x);else return getcol(rt<<1|1,x);
}
int ask(int x,int y){int fx = top[x], fy = top[y], res = 0;while(fx != fy){if(deep[fx] < deep[fy]) swap(fx,fy),swap(x,y);res += query(1,seg[fx],seg[x]);if(getcol(1,seg[fx]) == getcol(1,seg[par[fx]])) res--;x = par[fx]; fx = top[x];}if(deep[x] > deep[y]) swap(x,y);res += query(1,seg[x],seg[y]);return res;
}
int n,m;
int main(){scanf("%d%d",&n,&m);for(int i = 1;i <= n;i++) scanf("%d",a+i);for(int i = 1,x,y;i < n;i++){scanf("%d%d",&x,&y); addEdge(x,y,1); addEdge(y,x,1);}preHandle(); char op[4];for(int i = 1,x,y,z;i <= m;i++){scanf("%s",op);if(op[0] == 'Q'){scanf("%d%d",&x,&y);printf("%d\n",ask(x,y));}else{scanf("%d%d%d",&x,&y,&z);change(x,y,z);}}return 0;
}

「SDOI2014」旅行

题意简述
S 国有 N 个城市，编号从 1 到 N。城市间用 N−1 条双向道路连接，满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。为了方便，我们用不同的正整数代表各种宗教，S 国境内总共有 C 种不同的宗教。
S 国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S 国政府为每个城市标定了不同的旅行评级，旅行者们常会记下途中（包括起点和终点）留宿过的城市的评级总和或最大值。
在 S 国的历史上常会发生以下几种事件：

1、CC x c：城市 x 的居民全体改信了 c 教；

2、CW x w：城市 x 的评级调整为 w；

3、QS x y：一位旅行者从城市 x 出发，到城市 y，并记下了途中留宿过的城市的评级总和；

4、QM x y：一位旅行者从城市 x 出发，到城市 y，并记下了途中留宿过的城市的评级最大值。
由于年代久远，旅行者记下的数字已经遗失了，但记录开始之前每座城市的信仰与评级，还有事件记录本身是完好的。请根据这些信息，还原旅行者记下的数字。

为了方便，我们认为事件之间的间隔足够长，以致在任意一次旅行中，所有城市的评级和信仰保持不变。
解题思路
如果没有信仰，那就是简单的树链剖分模板题，但这题多了个信仰，正常思路是开数组存放对应信仰的评级，但是显然不现实，从空间角度来看。
这题用到了动态开点，和可持久化线段树类似，只需要稍微改一下线段树模板即可。

代码示例

#include
using namespace std;
typedef long long ll;
const int N = 1e5+10;
const int M = 2e5+10;
int head[N],ver[M],edge[M],nex[M],tot = 1;
void addEdge(int x,int y,int z){ver[++tot] = y,edge[tot] = z;nex[tot] = head[x], head[x] = tot;
}
int n,m;
int deep[N],par[N],size[N],top[N],seg[N],rev[N],son[N];
int vis[N],a[N],c[N];//a:初始评级 c:初始信仰
void dfs1(int x,int fa){deep[x] = deep[fa]+1;par[x] = fa;size[x] = 1;vis[x] = true;for(int i = head[x];i ;i = nex[i]){int y = ver[i], z = edge[i];if(vis[y] || y == fa) continue;dfs1(y,x);size[x] += size[y];if(size[y] > size[son[x]]) son[x] = y;}
}
void dfs2(int x,int fa){if(son[x]){seg[son[x]] = ++seg[0];rev[seg[0]] = son[x];top[son[x]] = top[x];dfs2(son[x],x);}for(int i = head[x];i;i = nex[i]){int y = ver[i],z = edge[i];if(top[y]) continue;seg[y] = ++seg[0]; rev[seg[0]] = y;top[y] = y; dfs2(y,x);}
}
struct SegmentTree{int ls,rs;ll mx,sum;SegmentTree(){ls = rs = mx = sum = 0;}#define ls(x) t[x].ls#define rs(x) t[x].rs#define mx(x) t[x].mx#define sum(x) t[x].sum
}t[N*20];
int root[N],sz = 1;//最多有多少个根节点
void preHandle(){dfs1(1,0);seg[0] = seg[1] = rev[1] = top[1] = 1;dfs2(1,0);
}
void Add(int &rt,int l,int r,int pos,ll val){if(!rt) rt = ++sz;mx(rt) = max(mx(rt),val); sum(rt) += val;if(l == r) return; int mid = l+r>>1;if(pos <= mid) Add(ls(rt),l,mid,pos,val);else Add(rs(rt),mid+1,r,pos,val);
}
void Delete(int rt,int l,int r,int pos){if(l == r){sum(rt) = mx(rt) = 0; return;}int mid = l+r>>1;if(pos <= mid) Delete(ls(rt),l,mid,pos);else Delete(rs(rt),mid+1,r,pos);sum(rt) = sum(ls(rt)) + sum(rs(rt));mx(rt) = max(mx(ls(rt)),mx(rs(rt)));
}
ll mx,sum;
void query(int rt,int L,int R,int l,int r){//  printf("%d %d %d %d %d\n",rt,L,R,l,r);if(!rt) return;if(l <= L && R <= r){//  printf("%d %d\n",mx(rt),sum(rt));mx = max(mx,mx(rt)); sum += sum(rt); return;}int mid = L+R>>1;if(l <= mid) query(ls(rt),L,mid,l,r);if(r > mid) query(rs(rt),mid+1,R,l,r);
}
void ask(int rt,int x,int y){/*返回x到y路径上信仰rt的评级最大值以及总和*/int fx = top[x],fy = top[y];while(fx != fy){if(deep[fx] < deep[fy]) swap(x,y),swap(fx,fy);query(rt,1,seg[0],seg[fx],seg[x]);x = par[fx]; fx = top[x];}if(deep[x] > deep[y]) swap(x,y);query(rt,1,seg[0],seg[x],seg[y]);
}
int main(){scanf("%d%d",&n,&m);for(int i = 1;i <= n;i++) scanf("%d%d",a+i,c+i);for(int i = 1,x,y;i < n;i++){scanf("%d%d",&x,&y);addEdge(x,y,1); addEdge(y,x,1);}preHandle();for(int i = 1;i <= n;i++)Add(root[c[i]],1,seg[0],seg[i],a[i]);char op[10];for(int i = 1,x,y;i <= m;i++){scanf("%s%d%d",op,&x,&y);if(op[1] == 'C'){Delete(root[c[x]],1,seg[0],seg[x]);Add(root[c[x] = y],1,seg[0],seg[x],a[x]);}else if(op[1] == 'W'){Delete(root[c[x]],1,seg[0],seg[x]);Add(root[c[x]],1,seg[0],seg[x],a[x] = y);}else{mx = sum = 0;//一起更新，少写代码，美滋滋ask(root[c[x]],x,y);if(op[1] == 'S') printf("%lld\n",sum);else printf("%lld\n",mx);}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！