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 >> 萌新求教,洛谷AC而且速度还行左右,BZOJtle
rourou @ 2018-07-03 09:33:24
[ Quote ] [ Edit ] [ Delete ] 1#

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cctype>

using namespace std;

int n,a,b,num[30050],m;

vector <int> g[30050];

int son[30050],depth[30050],fa[30050],size[30050];

int top[30050],ide[30050],rid[30050],cnt=0;

void dfs1(int u,int f)
{
fa[u]=f;
size[u]=1;
depth[u]=depth[f]+1;
for (int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if (v!=f)
{
dfs1(v,u);
size[u]+=size[v];
if (size[v]>size[son[u]])
son[u]=v;
}
}
}

void dfs2(int u,int fir)
{
//cout << u << " " << fir << endl;
top[u]=fir;
ide[u]=++cnt;
rid[ide[u]]=u;
if (!son[u])
return;
dfs2(son[u],fir);
for (int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if (v!=son[u] && v!=fa[u])
dfs2(v,v);
}
}

struct segtree
{
int l,r,val,vmax;
}t[150005];

void Push_Up(int id)
{
t[id].val=t[id*2].val+t[id*2+1].val;
t[id].vmax=max(t[id*2].vmax,t[id*2+1].vmax);
}

void Build(int id,int l,int r)
{
t[id].l=l;
t[id].r=r;
if (l==r)
{
t[id].val=num[rid[l]];
t[id].vmax=t[id].val;
return;
}
int mid=(l+r)/2;
Build(id*2,l,mid);
Build(id*2+1,mid+1,r);
Push_Up(id);
}

void Change(int id,int l,int r,int q,int value)
{
if (l==r)
{
t[id].val=value;
t[id].vmax=value;
return;
}
int mid=(l+r)/2;
if (q<=mid)
Change(id*2,l,mid,q,value);
else
Change(id*2+1,mid+1,r,q,value);
Push_Up(id);
}

int QuerySum(int id,int l,int r,int ql,int qr)
{
int ans=0;
if (ql<=l && r<=qr)
return t[id].val;
int mid=(l+r)/2;
if (ql<=mid)
ans+=QuerySum(id*2,l,mid,ql,qr);
if (qr>mid)
ans+=QuerySum(id*2+1,mid+1,r,ql,qr);
Push_Up(id);
return ans;
}

int QueryMax(int id,int l,int r,int ql,int qr)
{
int ans=-1e9;
if (ql<=l && r<=qr)
return t[id].vmax;
int mid=(l+r)/2;
if (ql<=mid)
ans=max(ans,QueryMax(id*2,l,mid,ql,qr));
if (qr>mid)
ans=max(ans,QueryMax(id*2+1,mid+1,r,ql,qr));
Push_Up(id);
return ans;
}

int LinkQuerySum(int u,int v)
{
int ans=0;
while (top[u]!=top[v])
{
if (depth[top[u]]<depth[top[v]])
swap(u,v);
ans+=QuerySum(1,1,n,ide[top[u]],ide[u]);
u=fa[top[u]];
}
if (depth[u]<depth[v])
swap(u,v);
ans+=QuerySum(1,1,n,ide[v],ide[u]);
return ans;
}

int LinkQueryMax(int u,int v)
{
int ans=-1e9;
while (top[u]!=top[v])
{
if (depth[top[u]]<depth[top[v]])
swap(u,v);
ans=max(ans,QueryMax(1,1,n,ide[top[u]],ide[u]));
u=fa[top[u]];
}
if (depth[u]<depth[v])
swap(u,v);
ans=max(ans,QueryMax(1,1,n,ide[v],ide[u]));
return ans;
}

int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-')f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}

int main()
{
n=read();
for (int i=1;i<n;i++)
{
int u,v;
u=read();v=read();
g[u].push_back(v);
g[v].push_back(u);
}
for (int i=1;i<=n;i++)
num[i]=read();
dfs1(1,0);
dfs2(1,1);
m=read();
Build(1,1,n);
while (m--)
{
string str;
cin >> str;
int x=read(),y=read();
if (str=="CHANGE")
Change(1,1,n,ide[x],y);
else
{
if (str=="QSUM")
printf("%d\n",LinkQuerySum(x,y));
if (str=="QMAX")
printf("%d\n",LinkQueryMax(x,y));
}
}
return 0;
}
nzhtl1477 @ 2018-07-03 14:13:08
[ Quote ] [ Edit ] [ Delete ] 2#
女装吧
strangers @ 2018-07-03 20:37:35
[ Quote ] [ Edit ] [ Delete ] 3#
女装吧
HuiFeng @ 2018-07-04 08:20:12
[ Quote ] [ Edit ] [ Delete ] 4#
女装吧
Leftist_Tree @ 2018-07-09 20:51:04
[ Quote ] [ Edit ] [ Delete ] 5#
女装吧
Ycrpro @ 2018-07-10 12:32:40
[ Quote ] [ Edit ] [ Delete ] 6#
Orz chen_zhe
RBQ @ 2018-07-10 15:20:06
[ Quote ] [ Edit ] [ Delete ] 7#
刚才是谁打断复读的?
strangers @ 2018-07-10 15:42:06
[ Quote ] [ Edit ] [ Delete ] 8#
刚才是谁打断复读的?
KingSann @ 2018-07-11 09:16:31
[ Quote ] [ Edit ] [ Delete ] 9#
刚才是谁打断复读的?
RyeCatcher @ 2018-07-11 12:00:00
[ Quote ] [ Edit ] [ Delete ] 10#
让我继续打断复读
[Top] [Previous Page] [Next Page]

HOME Back