NC20579. [SDOI2014]旅行
描述
输入描述
输入的第一行包含整数N，Q依次表示城市数和事件数。接下来N行，第i+l行两个整数Wi，Ci依次表示记录开始之前，城市i的评级和信仰。接下来N-1行每行两个整数x，y表示一条双向道路。接下来Q行，每行一个操作，格式如上所述。
输出描述
对每个QS和QM事件，输出一行，表示旅行者记下的数字。
示例1
输入:
5 6 3 1 2 3 1 2 3 3 5 1 1 2 1 3 3 4 3 5 QS 1 5 CC 3 1 QS 1 5 CW 3 3 QS 1 5 QM 2 4
输出:
8 9 11 3
C++(g++ 7.5.0) 解法, 执行用时: 534ms, 内存消耗: 45560K, 提交时间: 2023-02-14 21:50:09
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#define ll long long
using namespace std;
const int N=100005;
ll cnt,cnt1,cnt2,dfn[N],dep[N],sz[N],ans,head[N],fa[N],hs[N],top[N],rnk[N],n,root[N],q,d[N],c[N];
struct o
{
ll v,u;
}e[200005];
struct io
{
ll l,r,sum,ma;
}node[30000000];
void ud(ll &rt,ll l,ll r,ll w,ll va)
{
if(!rt) rt=++cnt2;
ll mid=(l+r)>>1;
if(l==r)
{
node[rt].sum=va;
node[rt].ma=va;
return;
}
if(w<=mid) ud(node[rt].l,l,mid,w,va);
else ud(node[rt].r,mid+1,r,w,va);
node[rt].sum=node[node[rt].l].sum+node[node[rt].r].sum;
node[rt].ma=max(node[node[rt].l].ma,node[node[rt].r].ma);
}
void qus(ll l,ll r,ll l1,ll r1,ll rt)
{
if(rt==0) return;
if(l1>=l&&r1<=r)
{
ans+=node[rt].sum;
return;
}
ll mid=(l1+r1)>>1;
if(l<=mid) qus(l,r,l1,mid,node[rt].l);
if(r>=mid+1) qus(l,r,mid+1,r1,node[rt].r);
}
void qusa(ll l,ll r,ll l1,ll r1,ll rt)
{
if(rt==0) return;
if(l1>=l&&r1<=r)
{
ans=max(ans,node[rt].ma);
return;
}
ll mid=(l1+r1)>>1;
if(l<=mid) qusa(l,r,l1,mid,node[rt].l);
if(r>=mid+1) qusa(l,r,mid+1,r1,node[rt].r);
}
void add(ll u,ll v)
{
cnt++;
e[cnt].u=head[u];
e[cnt].v=v;
head[u]=cnt;
}
void dfs1(ll u,ll f)
{
sz[u]=1;
fa[u]=f;
ll maxson=-1;
for(ll i=head[u];i;i=e[i].u)
{
ll v=e[i].v;
if(v!=f)
{
dep[v]=dep[u]+1;
dfs1(v,u);
sz[u]+=sz[v];
if(sz[v]>maxson)
{
hs[u]=v;
maxson=sz[v];
}
}
}
}
void dfs2(ll u,ll t)
{
top[u]=t;
cnt1++;
dfn[u]=cnt1;
rnk[dfn[u]]=u;
rnk[cnt1]=u;
if(hs[u]==0) return;
dfs2(hs[u],t);
for(ll i=head[u];i;i=e[i].u)
{
ll v=e[i].v;
if(v!=fa[u]&&v!=hs[u])
{
dfs2(v,v);
}
}
}
void op1(ll u,ll v,ll val)
{
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]]) swap(u,v);
qus(dfn[top[u]],dfn[u],1,n,root[val]);
u=fa[top[u]];
}
if(dfn[u]>dfn[v]) qus(dfn[v],dfn[u],1,n,root[val]);
else qus(dfn[u],dfn[v],1,n,root[val]);
}
void op2(ll u,ll v,ll val)
{
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]]) swap(u,v);
qusa(dfn[top[u]],dfn[u],1,n,root[val]);
u=fa[top[u]];
}
if(dfn[u]>dfn[v]) qusa(dfn[v],dfn[u],1,n,root[val]);
else qusa(dfn[u],dfn[v],1,n,root[val]);
}
int main()
{
cin>>n>>q;
for(ll i=1;i<=n;i++)
{
cin>>d[i]>>c[i];
}
for(ll i=1;i<n;i++)
{
ll x,y;
cin>>x>>y;
add(x,y);
add(y,x);
}
dfs1(1,0);
dfs2(1,1);
for(ll i=1;i<=n;i++)
{
ud(root[c[i]],1,n,dfn[i],d[i]);
}
char zf[3];
for(ll i=1;i<=q;i++)
{
ll x,y;
cin>>zf>>x>>y;
if(zf[1]=='C')
{
ud(root[c[x]],1,n,dfn[x],0);
c[x]=y;
ud(root[y],1,n,dfn[x],d[x]);
}
if(zf[1]=='W')
{
d[x]=y;
ud(root[c[x]],1,n,dfn[x],y);
}
if(zf[1]=='S')
{
ans=0;
op1(x,y,c[x]);
cout<<ans<<'\n';
}
if(zf[1]=='M')
{
ans=0;
op2(x,y,c[x]);
cout<<ans<<'\n';
}
}
return 0;
}
C++ 解法, 执行用时: 597ms, 内存消耗: 26312K, 提交时间: 2022-06-26 18:13:02
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 1;
struct node{
int l,r,sum,max;
}tree[maxn << 4];
struct edge{
int to,next;
}e[maxn << 1];
int head[maxn],cnt,w[maxn],c[maxn],Size[maxn],son[maxn],f[maxn],d[maxn];
int top[maxn],id[maxn],rk[maxn],root[maxn],x,y,qsum,qmax;
void add(const int &a,const int &b){
cnt++;
e[cnt].to = b;
e[cnt].next = head[a];
head[a] = cnt;
}
void dfs1(const int &u){
d[u] = d[f[u]] + 1;
Size[u] = 1;
for (int i = head[u];i;i = e[i].next){
int &v = e[i].to;
if (v != f[u]){
f[v] = u;
dfs1(v);
Size[u] += Size[v];
if (Size[v] > Size[son[u]])
son[u] = v;
}
}
}
void dfs2(const int &u){
id[u] = ++id[0];
rk[id[0]] = u;
if (!son[u])return;
top[son[u]] = top[u];
dfs2(son[u]);
for (int i = head[u];i;i = e[i].next){
int &v = e[i].to;
if (!top[v]){
top[v] = v;
dfs2(v);
}
}
}
void push(const int &k){
tree[k].sum = tree[tree[k].l].sum + tree[tree[k].r].sum;
tree[k].max = max(tree[tree[k].l].max,tree[tree[k].r].max);
}
void C(int &k,int l,int r,const int &pos){
if (!k)k = ++cnt;
if (l == r){
tree[k].sum = tree[k].max = w[rk[pos]];
return;
}
int mid = l + r >> 1;
if (pos <= mid)
C(tree[k].l,l,mid,pos);
else C(tree[k].r,mid + 1,r,pos);
push(k);
}
void del(const int &k,int l,int r){
if (l == r){
tree[k].sum = tree[k].max = 0;
return;
}
int mid = l + r >> 1;
if (id[x] <= mid)
del(tree[k].l,l,mid);
else del(tree[k].r,mid + 1,r);
push(k);
}
void Q(const int &k,int l,int r,const int &a,const int &b){
if (a <= l && r <= b){
qsum += tree[k].sum;
qmax = max(qmax,tree[k].max);
return;
}else if(l == r)
return;
int mid = l + r >> 1;
if (a <= mid)
Q(tree[k].l,l,mid,a,b);
if (b > mid)
Q(tree[k].r,mid + 1,r,a,b);
}
int main(){
int n,q,i;
cin>>n>>q;
for (i = 1;i <= n;i++)
cin>>w[i]>>c[i];
for (i = 1;i < n;i++){
cin>>x>>y;
add(x,y);
add(y,x);
}
dfs1(1);
top[1] = 1;
dfs2(1);
cnt = 0;
for (i = 1;i <= n;i++)
C(root[c[i]],1,n,id[i]);
char op[3];
while (q--){
cin>>op>>x>>y;
if (op[0] == 'C'){
del(root[c[x]],1,n);
if (op[1] == 'C')
c[x] = y;
else w[x] = y;
C(root[c[x]],1,n,id[x]);
}else{
i = c[x];
qsum = qmax = 0;
while (top[x] != top[y]){
if (d[top[x]] < d[top[y]])
swap(x,y);
Q(root[i],1,n,id[top[x]],id[x]);
x = f[top[x]];
}
if (d[x] > d[y])
swap(x,y);
Q(root[i],1,n,id[x],id[y]);
cout<<(op[1] == 'S' ? qsum : qmax)<<endl;
}
}
return 0;
}