F.A.Qs | Home | ProblemSet | Status | Ranklist | Contest | Login | Register |
---|
Problem 1036 >> 萌新求教,洛谷AC而且速度还行左右,BZOJtle |
rourou @ 2018-07-03 09:33:24
#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
女装吧
|
strangers @ 2018-07-03 20:37:35
女装吧
|
HuiFeng @ 2018-07-04 08:20:12
女装吧
|
Leftist_Tree @ 2018-07-09 20:51:04
女装吧
|
Ycrpro @ 2018-07-10 12:32:40
Orz chen_zhe
|
RBQ @ 2018-07-10 15:20:06
刚才是谁打断复读的?
|
strangers @ 2018-07-10 15:42:06
刚才是谁打断复读的?
|
KingSann @ 2018-07-11 09:16:31
刚才是谁打断复读的?
|
RyeCatcher @ 2018-07-11 12:00:00
让我继续打断复读
|