动态开点线段树
标题链接思路
对于树的线路题目可以用树剖来分别成一段一段的一连区间，但由于只记录这些区间某个信仰的权值，而且只有单点修改，所以我们思量给每个信仰都开一个线段树，也就是开1e5个线段树（类似主席树的写法，开个root数组来记录每个线段树的根，然后布局体来存那些点和他们的信息，左右儿子），用每个线段树来维护各个信仰的区间和与区间最大值。
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const int N=1e5+10;
const int mod=1e9+7;
#define fi first
#define se second
int n,q;
int w,c;
vector<int> e;
//树剖
int siz,dep,newid,newc,neww;
int treecut,son,fa,top;
void dfs(int x,int f){
siz=1;
fa=f;
dep=dep+1;
for(auto y:e){
if(y==f)
continue;
dfs(y,x);
siz+=siz;
if(siz>siz])
son=y;
}
}
void dfs(int x,int f,int id){
newid=++treecut;
top=id;//是用原节点x来记录top，因为top是在树在lca的，树上的信息都记录的x，treecut已经转化成链了
newc=c;//这些都是维护新下标的信息
neww=w;
if(son){
dfs(son,x,id);//仍然是id，表示这条重链的头都是id
}
for(auto y:e){
if(y==f||y==son) //重儿子不要再进
continue;
dfs(y,x,y);
}
}
//线段树
int root,treecnt;
struct node{
int l,r,maxx,sum;
}tree;
void pushup(int l,int r,int &k){
int ls=tree.l,rs=tree.r;
tree.maxx=max(tree.maxx,tree.maxx);
tree.sum=tree.sum+tree.sum;
}
void modify(int l,int r,int &k,int x,int value){
if(!k) k=++treecnt;//k是引用，为0表示为NULL，要创节点
if(l==r){
tree.maxx=tree.sum=value;
return;
}
int mid=(l+r)>>1;
if(x<=mid) modify(l,mid,tree.l,x,value);
else modify(mid+1,r,tree.r,x,value);
pushup(l,r,k);
}
int querysum(int l,int r,int &k,int x,int y){
if(x<=l&&y>=r)
return tree.sum;
int mid=(l+r)>>1;
int res=0;
if(x<=mid) res+=querysum(l,mid,tree.l,x,y);
if(y>mid) res+=querysum(mid+1,r,tree.r,x,y);
return res;
}
int querymax(int l,int r,int &k,int x,int y){
if(x<=l&&y>=r)
return tree.maxx;
int mid=(l+r)>>1;
int res=0;
if(x<=mid) res=max(res,querymax(l,mid,tree.l,x,y));
if(y>mid) res=max(res,querymax(mid+1,r,tree.r,x,y));
return res;
}
//lca
int cc;//表示lca的子树是哪个信仰子树
int lcasum(int a,int b){
int res=0;
while(top!=top){//不在同一重链
if(dep]<dep])//保证a所在链的dep要大
swap(a,b);
res+=querysum(1,n,root,newid],newid);
a=fa];//要fa来跳出这条链
}
if(newid>newid)
swap(a,b);
res+=querysum(1,n,root,newid,newid);
return res;
}
int lcamax(int a,int b){
int res=0;
while(top!=top){
if(dep]<dep])
swap(a,b);
res=max(res,querymax(1,n,root,newid],newid));
a=fa];
}
if(newid>newid)
swap(a,b);
res=max(res,querymax(1,n,root,newid,newid));
return res;
}
void solve(){
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>w>>c;
}
for(int i=1;i<n;i++){
int a,b;cin>>a>>b;
e.push_back(b);
e.push_back(a);
}
dfs(1,0);
dfs(1,0,1);
for(int i=1;i<=n;i++){//全用新的了...
modify(1,n,root]],newid,neww]);
}
while(q--){
string s;
cin>>s;
int x,y;
cin>>x>>y;
cc=newc];//信仰
if(s=="CC"){
int t=querysum(1,n,root]],newid,newid);
modify(1,n,root]],newid,0);
modify(1,n,root,newid,t);
newc]=y;//记得修改信仰
}
else if(s=="CW"){
modify(1,n,root]],newid,y);
neww]=y;
}
else if(s=="QS"){
cout<<lcasum(x,y)<<endl;
}
else{
cout<<lcamax(x,y)<<endl;
}
}
}
signedmain(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t=1;
//cin>>t;
while(t--){
solve();
}
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]