F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
大视野在线测评-欢迎您
[ New Thread ]
Problem 1036 >> 哪位知道这个代码为什么错了
Ferryman @ 2018-12-21 17:21:07
[ Quote ] [ Edit ] [ Delete ] 1#
#include<bits/stdc++.h>
using namespace std;
#define many 30005
struct t{
int data,last;
}ljb[many];//邻接表
string s;
int m,head[many],inc,n,num[many];
int father[many],dep[many],son[many],size[many],top[many];
int seg[many],rev[many];
int ans_maxx,ans_sum;
/*
faher父亲,dep深度,inc时间戳,son重儿子
size子树大小,top重路径深度最小,seg线段树下标
rev线段树中第x个在树中编号
*/
struct Node{
int maxx,sum;
Node *ls,*rs;
Node(){
ls=rs=NULL;
maxx=sum=0;
}
}tr[many*2+5],*root,*tail=tr;
void add(int a,int b)
{
inc++;
ljb[inc].data=b;
ljb[inc].last=head[a];
head[a]=inc;
return;
}
void dfs1(int u,int f)
{
size[u]=1;
father[u]=f;
dep[u]=dep[f]+1;
for(int i=head[u];i;i=ljb[i].last)
{
int x=ljb[i].data;
if(x==f) continue;
dfs1(x,u);
size[u]+=size[x];
if(size[x]>size[son[u]]) son[u]=x;
}
return;
}
void dfs2(int u,int f)
{
if(son[u])
{//表示有重儿子
inc++;
seg[son[u]]=inc;
rev[inc]=son[u];
top[son[u]]=top[u];
dfs2(son[u],u);
}
for(int i=head[u];i;i=ljb[i].last)
{
int x=ljb[i].data;
if(!top[x]&&x!=0)
{
inc++;
seg[x]=inc;
rev[inc]=x;
top[x]=x;
dfs2(x,u);
}
}
return;
}
Node *build(int l,int r)
{
Node *nd=++tail;
if(l==r)
{
nd->maxx=nd->sum=num[seg[l]];
return nd;
}
int mid=(l+r)>>1;
nd->ls=build(l,mid);
nd->rs=build(mid+1,r);
nd->maxx=max(nd->ls->maxx,nd->rs->maxx);
nd->sum=nd->ls->sum+nd->rs->sum;
return nd;
}
void modify(Node*nd,int l,int r,int pos,int val)
{//单点修改
if(l==r){
nd->maxx=val;
nd->sum=val;
return;
}
int mid=(l+r)>>1;
if(mid>=pos) modify(nd->ls,l,mid,pos,val);
else modify(nd->rs,mid+1,r,pos,val);
nd->maxx=max(nd->ls->maxx,nd->rs->maxx);
nd->sum=nd->ls->sum+nd->rs->sum;
return;
}
void query(Node *nd,int l,int r,int x,int y)
{//x,y为要询问的区间的下标
if(l>=x&&y>=r){
ans_maxx=max(ans_maxx,nd->maxx);
ans_sum+=nd->sum;
return;
}
int mid=(l+r)>>1;
if(y<=mid){
query(nd->ls,l,mid,x,y);
return;
}
if(x>=mid+1){
query(nd->rs,mid+1,r,x,y);
return;
}
query(nd->ls,l,mid,x,y);
query(nd->rs,mid+1,r,x,y);
return;
}
void ask(int x,int y)
{
ans_sum=ans_maxx=0;
int fx=top[x],fy=top[y];
while(fx!=fy)
{
if(dep[fx]<dep[fy]) {
swap(fx,fy);
swap(x,y);
}
query(root,1,m,seg[fx],seg[x]);
x=father[fx];fx=top[x];
}
if(dep[x]>dep[y]) swap(x,y);
query(root,1,m,seg[x],seg[y]);
return;
}
int main()
{
//freopen("test.in","r",stdin);
//freopen("ans.out","w",stdout);
scanf("%d",&m);
for(int i=1;i<m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
for(int i=1;i<=m;i++)
scanf("%d",&num[i]);
dfs1(1,0);
inc=1;
seg[1]=inc;
rev[inc]=1;
top[1]=1;
dfs2(1,0);
root=build(1,m);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int a,b;
cin>>s>>a>>b;
if(s[0]=='C') {
modify(root,1,m,seg[a],b);
continue;
}
if(s[0]=='Q') ask(a,b);
if(s[1]=='S') {
printf("%d\n",ans_sum);
continue;
}
printf("%d\n",ans_maxx);
}
return 0;
}
[Top] [Previous Page] [Next Page]

HOME Back