顺德网站制作案例机构,常州哪家做网站好,办公空间设计公司排名,杭州做网站的公司有哪些正题
题目链接:https://www.luogu.com.cn/problem/P3313 题目大意 nnn个点的一棵树#xff0c;每个点有一个颜色和权值#xff0c;有操作
修改一个点的权值修改一个点的颜色询问一条路径的某颜色的权值和询问一条路径的某颜色的权值最大值 解题思路
询问路径直接树剖先每个点有一个颜色和权值有操作
修改一个点的权值修改一个点的颜色询问一条路径的某颜色的权值和询问一条路径的某颜色的权值最大值 解题思路
询问路径直接树剖先然后对于每个颜色开一个动态开点的线段树单点修改所以不会炸空间。
然后就是树链剖分的板子了。
时间复杂度O(nlog2n)O(n\log^2n )O(nlog2n) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e510;
struct node{int to,next;
}a[N1];
int n,q,cnt,tot,w[N],c[N],ls[N],rt[N];
int fa[N],dep[N],siz[N],top[N],son[N],rfn[N];
struct SegTree{int cnt,w[N6],v[N6],ls[N6],rs[N6];void Change(int x,int L,int R,int pos,int val){if(!x)xcnt;if(LR){w[x]val;v[x]val;return;}int mid(LR)1;if(posmid)Change(ls[x],L,mid,pos,val);else Change(rs[x],mid1,R,pos,val);v[x]max(v[ls[x]],v[rs[x]]);w[x]w[ls[x]]w[rs[x]];return;}int Ask(int x,int L,int R,int l,int r){if(!x)return 0;if(LlRr)return w[x];int mid(LR)1;if(rmid)return Ask(ls[x],L,mid,l,r);if(lmid)return Ask(rs[x],mid1,R,l,r);return Ask(ls[x],L,mid,l,mid)Ask(rs[x],mid1,R,mid1,r);}int Query(int x,int L,int R,int l,int r){if(!x)return 0;if(LlRr)return v[x];int mid(LR)1;if(rmid)return Query(ls[x],L,mid,l,r);if(lmid)return Query(rs[x],mid1,R,l,r);return max(Query(ls[x],L,mid,l,mid),Query(rs[x],mid1,R,mid1,r));}
}T;
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs1(int x){siz[x]1;dep[x]dep[fa[x]]1;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa[x])continue;fa[y]x;dfs1(y);siz[x]siz[y];if(siz[y]siz[son[x]])son[x]y;}return;
}
void dfs2(int x){rfn[x]cnt;T.Change(rt[c[x]],1,n,cnt,w[x]);if(son[x]){top[son[x]]top[x];dfs2(son[x]);}for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa[x]||yson[x])continue;top[y]y;dfs2(y);}return;
}
int main()
{scanf(%d%d,n,q);for(int i1;in;i)scanf(%d%d,w[i],c[i]);for(int i1;in;i){int x,y;scanf(%d%d,x,y);addl(x,y);addl(y,x);}dfs1(1);top[1]1;dfs2(1);while(q--){char op[3];int x,y;scanf(%s%d%d,op,x,y);if(op[0]Cop[1]C){T.Change(rt[c[x]],1,n,rfn[x],-w[x]);T.Change(rt[y],1,n,rfn[x],w[x]);c[x]y;}else if(op[0]Cop[1]W){T.Change(rt[c[x]],1,n,rfn[x],y-w[x]);w[x]y;}else if(op[0]Qop[1]S){int zc[x],ans0;while(top[x]!top[y]){if(dep[top[x]]dep[top[y]])swap(x,y);ansT.Ask(rt[z],1,n,rfn[top[x]],rfn[x]);xfa[top[x]];}if(dep[x]dep[y])swap(x,y);ansT.Ask(rt[z],1,n,rfn[x],rfn[y]);printf(%d\n,ans);}else if(op[0]Qop[1]M){int zc[x],ans0;while(top[x]!top[y]){if(dep[top[x]]dep[top[y]])swap(x,y);ansmax(ans,T.Query(rt[z],1,n,rfn[top[x]],rfn[x]));xfa[top[x]];}if(dep[x]dep[y])swap(x,y);ansmax(ans,T.Query(rt[z],1,n,rfn[x],rfn[y]));printf(%d\n,ans);}}return 0;
}
