如何分析网站流量,第一营销网,东莞振安保安公司,wordpress腾讯云点播插件传送门 省选前水一发 这题一开始看标签是主席树……后来……这题和主席树有啥关系…… 可以想到对于每种宗教用树剖线段树维护即可。然后因为空间不够要动态开点。然后改宗教#xff0c;改评级的#xff0c;把原来的点删了再插一个新点就可以了。查询最大值#xff0c;和就直…传送门 省选前水一发 这题一开始看标签是主席树……后来……这题和主席树有啥关系…… 可以想到对于每种宗教用树剖线段树维护即可。然后因为空间不够要动态开点。然后改宗教改评级的把原来的点删了再插一个新点就可以了。查询最大值和就直接线段树维护。 当树剖板子练习了。 #includebits/stdc.h
#define rep(i,a,n) for(int i a;i n;i)
#define per(i,n,a) for(int i n;i a;i--)
#define enter putchar(\n)
#define pr pairint,int
#define mp make_pair
#define fi first
#define sc second
using namespace std;
typedef long long ll;
const int M 100005;
const int N 2000005;
const int INF 0x3f3f3f3f;int read()
{int ans 0,op 1;char ch getchar();while(ch 0 || ch 9) {if(ch -) op -1;ch getchar();}while(ch 0 ch 9) ans ans * 10 ch - 0,ch getchar();return ans * op;
}int n,m,w[M],c[M],head[M],ecnt,dep[M],hson[M],top[M],idx,dfn[M],rk[M],fa[M];
int x,y,size[M],cnt,root[M],k,q;
char ch[5];struct tree
{int lc,rc,val,sum;
}t[M5];struct edge
{int next,to,from;
}e[M1];void add(int x,int y){e[ecnt] {head[x],y,x},head[x] ecnt;}void dfs1(int x,int f)
{dep[x] dep[f] 1,size[x] 1,fa[x] f;for(int i head[x];i;i e[i].next){if(e[i].to f) continue;dfs1(e[i].to,x);size[x] size[e[i].to];if(size[e[i].to] size[hson[x]]) hson[x] e[i].to;}
}void dfs2(int x,int t)
{dfn[x] idx,rk[idx] x,top[x] t;if(hson[x]) dfs2(hson[x],t);for(int i head[x];i;i e[i].next){if(e[i].to hson[x] || e[i].to fa[x]) continue;dfs2(e[i].to,e[i].to);}
}void pushup(int p)
{t[p].val max(t[t[p].lc].val,t[t[p].rc].val);t[p].sum t[t[p].lc].sum t[t[p].rc].sum;
}
void pushdown(int p){t[p].sum t[p].val 0;}void insert(int p,int l,int r,int pos,int val)
{if(!p) p cnt;if(l r) {t[p].sum t[p].val val;return;}int mid (lr) 1;if(pos mid) insert(t[p].lc,l,mid,pos,val);else insert(t[p].rc,mid1,r,pos,val);pushup(p);
}void del(int p,int l,int r,int pos)
{if(!p) return;if(l r) {pushdown(p);return;}int mid (lr) 1;if(pos mid) del(t[p].lc,l,mid,pos);else del(t[p].rc,mid1,r,pos);pushup(p);
}int query(int p,int l,int r,int kl,int kr)
{if(!p) return 0;if(l kl r kr) return t[p].sum;int mid (lr) 1;if(kr mid) return query(t[p].lc,l,mid,kl,kr);else if(kl mid) return query(t[p].rc,mid1,r,kl,kr);else return query(t[p].lc,l,mid,kl,mid) query(t[p].rc,mid1,r,mid1,kr);
}int ask(int p,int l,int r,int kl,int kr)
{if(!p) return 0;if(l kl r kr) return t[p].val;int mid (lr) 1;if(kr mid) return ask(t[p].lc,l,mid,kl,kr);else if(kl mid) return ask(t[p].rc,mid1,r,kl,kr);else return max(ask(t[p].lc,l,mid,kl,mid),ask(t[p].rc,mid1,r,mid1,kr));
}int srange(int x,int y)
{int cur 0,k c[x];while(top[x] ! top[y]){if(dep[top[x]] dep[top[y]]) swap(x,y);cur query(root[k],1,n,dfn[top[x]],dfn[x]);x fa[top[x]];}if(dep[x] dep[y]) swap(x,y);cur query(root[k],1,n,dfn[x],dfn[y]);return cur;
}int mrange(int x,int y)
{int cur 0,k c[x];while(top[x] ! top[y]){if(dep[top[x]] dep[top[y]]) swap(x,y);cur max(cur,ask(root[k],1,n,dfn[top[x]],dfn[x]));x fa[top[x]];}if(dep[x] dep[y]) swap(x,y);cur max(cur,ask(root[k],1,n,dfn[x],dfn[y]));return cur;
}int main()
{n read(),q read();rep(i,1,n) w[i] read(),c[i] read();rep(i,1,n-1) x read(),y read(),add(x,y),add(y,x);dfs1(1,0),dfs2(1,1);rep(i,1,n) insert(root[c[i]],1,n,dfn[i],w[i]);while(q--){scanf(%s,ch);if(ch[1] C){x read(),k read();del(root[c[x]],1,n,dfn[x]),c[x] k;insert(root[c[x]],1,n,dfn[x],w[x]);}if(ch[1] W){x read(),k read();del(root[c[x]],1,n,dfn[x]),w[x] k;insert(root[c[x]],1,n,dfn[x],w[x]);}if(ch[1] S){x read(),y read();printf(%d\n,srange(x,y));}if(ch[1] M){x read(),y read();printf(%d\n,mrange(x,y));}}return 0;
}转载于:https://www.cnblogs.com/captain1/p/10659250.html
