[문제 풀이] luoguP3313_여행
#include
#define mid ((l+r)>>1)
using namespace std;
const int maxn=100009;
int n,m,w[maxn],c[maxn],tot;
struct node{
int v,nxt;
}e[maxn<<1];
int head[maxn],cnt;
inline void add(int u,int v){
e[++cnt].v=v;e[cnt].nxt=head[u];head[u]=cnt;
}
int fa[maxn],dep[maxn],siz[maxn],son[maxn],dfn[maxn],id[maxn],top[maxn];
void dfs1(int x,int f){
siz[x]=1;dep[x]=dep[f]+1;fa[x]=f;
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].v;if(y==f)continue;
dfs1(y,x);
siz[x]+=siz[y];
if(siz[y]>siz[son[x]])son[x]=y;
}
}
void dfs2(int x,int tp){
top[x]=tp;
dfn[x]=++tot;
id[tot]=x;
if(!son[x])return;
dfs2(son[x],tp);
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].v;if(y==fa[x]||y==son[x])continue;
dfs2(y,y);
}
}
int root[maxn],ls[maxn*30],rs[maxn*30];
struct ttt{
int mx,sum;
}t[maxn*30];
inline void upd(int x){
t[x].sum=t[ls[x]].sum+t[rs[x]].sum;
t[x].mx=max(t[ls[x]].mx,t[rs[x]].mx);
}
inline void change(int &x,int l,int r,int pos,int val){//dfs pos, val
if(!x)x=++tot;
t[x].mx=max(t[x].mx,val),t[x].sum+=val;
if(l==r)return;
if(pos<=mid)change(ls[x],l,mid,pos,val);
else change(rs[x],mid+1,r,pos,val);
}
inline void del(int &x,int l,int r,int pos){
if(l==r){
t[x].sum=t[x].mx=0;return;
}
if(pos<=mid)del(ls[x],l,mid,pos);
else del(rs[x],mid+1,r,pos);
upd(x);
}
inline int qSum(int x,int l,int r,int L,int R){
if(L<=l&&r<=R)return t[x].sum;
int ans=0;
if(L<=mid)ans+=qSum(ls[x],l,mid,L,R);
if(R>mid)ans+=qSum(rs[x],mid+1,r,L,R);
return ans;
}
inline int qMx(int x,int l,int r,int L,int R){
if(L<=l&&r<=R)return t[x].mx;
int ans=0;
if(L<=mid)ans=max(ans,qMx(ls[x],l,mid,L,R));
if(R>mid)ans=max(ans,qMx(rs[x],mid+1,r,L,R));
return ans;
}
inline int qMxRoute(int x,int y,int val){
int ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
ans=max(ans,qMx(root[val],1,n,dfn[top[x]],dfn[x]));
x=fa[top[x]];
}
if(dep[x]<dep[y])swap(x,y);
ans=max(ans,qMx(root[val],1,n,dfn[y],dfn[x]));
return ans;
}
inline int qSumRoute(int x,int y,int val){
int ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
ans+=qSum(root[val],1,n,dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
if(dep[x]<dep[y])swap(x,y);
ans+=qSum(root[val],1,n,dfn[y],dfn[x]);
return ans;
}
int main(){
// freopen("test.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d%d",&w[i],&c[i]);
for(int i=1,u,v;i){
scanf("%d%d",&u,&v);add(u,v);add(v,u);
}
dfs1(1,0);dfs2(1,1);
for(int i=1;i<=n;i++)change(root[c[i]],1,n,dfn[i],w[i]);
char op[10];
for(int i=1,x,y;i<=m;i++){
scanf("%s",op);
scanf("%d%d",&x,&y);
if(op[1]=='C'){
del(root[c[x]],1,n,dfn[x]);
change(root[y],1,n,dfn[x],w[x]);
c[x]=y;
}
else if(op[1]=='W'){
del(root[c[x]],1,n,dfn[x]);
change(root[c[x]],1,n,dfn[x],y);
w[x]=y;
}
else if(op[1]=='S')printf("%d
",qSumRoute(x,y,c[x]));
else printf("%d
",qMxRoute(x,y,c[x]));
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.