| 记录编号 |
374071 |
评测结果 |
AAAAAAAAAAA |
| 题目名称 |
[河南省队2016]无根树 |
最终得分 |
100 |
| 用户昵称 |
 苦读依旧 |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
1.161 s |
| 提交时间 |
2017-02-22 11:14:20 |
内存使用 |
29.57 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
using namespace std;
struct E{
int l,r;
int lch,rch;
} t[520000];
struct Q{
int l,r;
} tr[420000];
struct q{
int from;
int to;
int next;
} e[220000];
int tot=0;
int ma[420000];
int dep[120000];
int head[120000];
int fa[120000];
int size[120000];
int son[120000];
int a[120000];
int num[120000];
int top[120000];
int tid[120000];
int pos[120000];
bool vis[120000];
int lx[520000];
int mx[520000];
int rx[520000];
int sum[520000];
int c[120000];
int root[120000];
int bl[120000];
int rt=0;
int tt=0;
int k=0;
void insert(int x,int y)
{
++tot; e[tot].from=x; e[tot].to=y;
e[tot].next=head[x]; head[x]=tot;
}
void update(int now)
{
int lch=t[now].lch; int rch=t[now].rch;
sum[now]=sum[lch]+sum[rch];
lx[now]=max(lx[lch],sum[lch]+lx[rch]);
rx[now]=max(rx[rch],sum[rch]+rx[lch]);
mx[now]=max(rx[lch]+lx[rch],max(mx[lch],mx[rch]));
}
void read(int &x)
{
char c; bool flag=0;
while((c=getchar())<'0'||c>'9') {
if(c=='-') flag=1;
}
x=c-'0';
while((c=getchar())<='9'&&c>='0') {
x=(x<<1)+(x<<3)+c-'0';
}
if(flag) x=-x;
}
void dfs1(int x,int last)
{
size[x]=1; int mxm=0;
for(int i=head[x];i;i=e[i].next) {
if(e[i].to!=last) {
fa[e[i].to]=x;
dep[e[i].to]=dep[x]+1;
dfs1(e[i].to,x);
size[x]+=size[e[i].to];
if(size[e[i].to]>mxm) {
mxm=size[e[i].to];
son[x]=e[i].to;
}
}
}
}
void dfs2(int x,int ancestor)
{
vis[x]=1; top[x]=ancestor; num[ancestor]++; tid[++tt]=x; pos[x]=tt;
if(!son[x]) return;
dfs2(son[x],ancestor);
for(int i=head[x];i;i=e[i].next) {
if(e[i].to!=son[x]&&!vis[e[i].to]) {
c[++rt]=e[i].to;
dfs2(e[i].to,e[i].to);
}
}
}
void update1(int now)
{
ma[now]=max(ma[now*2],ma[now*2+1]);
}
void build1(int now,int l,int r)
{
tr[now].l=l; tr[now].r=r;
int mid=(l+r)>>1;
if(l==r) {
// cout<<mx[root[l]]<<endl;
ma[now]=mx[root[l]];
return;
}
build1(now*2,l,mid); build1(now*2+1,mid+1,r);
update1(now);
}
void update_point1(int now,int x,int v)
{
int l=tr[now].l; int r=tr[now].r;
int mid=(l+r)>>1;
if(l==r) {
ma[now]=v;
return;
}
if(x<=mid) update_point1(now*2,x,v);
else update_point1(now*2+1,x,v);
update1(now);
}
int build(int tg,int l,int r)
{
int now=++k; t[now].l=l; t[now].r=r;
int mid=(l+r)>>1;
if(l==r) {
// cout<<l<<" "<<a[tid[l]]<<endl;
bl[l]=tg; lx[now]=a[tid[l]]; sum[now]=a[tid[l]];
mx[now]=a[tid[l]]; rx[now]=a[tid[l]];
return now;
}
t[now].lch=build(tg,l,mid); t[now].rch=build(tg,mid+1,r);
update(now);
return now;
}
void update_point(int now,int x,int v)
{
int l=t[now].l; int r=t[now].r;
int mid=(l+r)>>1;
if(l==r) {
lx[now]=v; sum[now]=v; mx[now]=v; rx[now]=v;
return;
}
if(x<=mid) update_point(t[now].lch,x,v);
else update_point(t[now].rch,x,v);
update(now);
}
void addtion(int now,int x,int v)
{
int l=t[now].l; int r=t[now].r;
int mid=(l+r)>>1;
if(l==r) {
mx[now]+=v; lx[now]+=v; rx[now]+=v; sum[now]+=v;
return;
}
if(x<=mid) addtion(t[now].lch,x,v);
else addtion(t[now].rch,x,v);
update(now);
}
/*void solve1(int x)
{
int y=x;
while(top[y]!=1) {
y=top[y];
if(lx[root[bl[pos[y]]]]>0) {
addtion(root[bl[pos[fa[y]]]],pos[fa[y]],lx[root[bl[pos[y]]]]);
update_point1(1,bl[pos[fa[y]]],mx[root[bl[pos[fa[y]]]]]);
} else {
break;
}
y=fa[y];
}
}*/
void solve(int x,int last)
{
int y=x; int cl;
while(top[y]!=1) {
y=top[y];
/* if(lx[root[bl[pos[y]]]]>0) {
// cout<<" "<<lx[root[bl[pos[y]]]]<<endl;//
// update_point(root[bl[pos[fa[y]]]],pos[fa[y]],a[fa[y]]+lx[root[bl[pos[y]]]]);
cl=lx[root[bl[pos[fa[y]]]]];
addtion(root[bl[pos[fa[y]]]],pos[fa[y]],lx[root[bl[pos[y]]]]-max(last,0));
// cout<<root[bl[pos[fa[y]]]]<<" "<<mx[root[bl[pos[fa[y]]]]]<<endl;
update_point1(1,bl[pos[fa[y]]],mx[root[bl[pos[fa[y]]]]]);
last=cl;
} else {
addtion(root[bl[pos[fa[y]]]],pos[fa[y]],0-max(last,0));
update_point1(1,bl[pos[fa[y]]],mx[root[bl[pos[fa[y]]]]]);
break;
}*/
cl=lx[root[bl[pos[fa[y]]]]];
addtion(root[bl[pos[fa[y]]]],pos[fa[y]],max(0,lx[root[bl[pos[y]]]])-max(last,0));
update_point1(1,bl[pos[fa[y]]],mx[root[bl[pos[fa[y]]]]]);
last=cl;
y=fa[y];
}
}
int zz=0;
void Query(int now,int x)
{
int l=t[now].l; int r=t[now].r;
int mid=(l+r)>>1;
if(l==r) {
zz=now;
return;
}
if(x<=mid) Query(t[now].lch,x);
else Query(t[now].rch,x);
}
void dfs(int x,int fa)
{
for(int i=head[x];i;i=e[i].next) {
if(e[i].to!=fa) {
dfs(e[i].to,x);
if(bl[pos[e[i].to]]!=bl[pos[x]]&&c[bl[pos[e[i].to]]]==e[i].to) {
addtion(root[bl[pos[x]]],pos[x],max(lx[root[bl[pos[e[i].to]]]],0));
update_point1(1,bl[pos[x]],mx[root[bl[pos[x]]]]);
}
}
}
}
int main()
{
freopen("nortree.in","r",stdin);
freopen("nortree.out","w",stdout);
int n; read(n); int m; read(m);// scanf("%d",&n);
for(int i=1;i<=n;++i) {
int x; read(x); a[i]=x;
}
for(int i=1;i<=n-1;++i) {
int x,y;// scanf("%d%d",&x,&y);
read(x); read(y);
insert(x,y); insert(y,x);
}
c[++rt]=1; dfs1(1,0); dfs2(1,1);
for(int i=1;i<=rt;++i) {
root[i]=build(i,pos[c[i]],pos[c[i]]+num[c[i]]-1);
}
build1(1,1,rt);
dfs(1,0);
// for(int i=rt;i>=1;--i) {
//if(fa[c[i]]&&lx[root[i]]>0) {
//update_point(root[bl[pos[fa[c[i]]]]],pos[fa[c[i]]],a[fa[c[i]]]+lx[root[i]]);
// solve(c[i],0);
//}
// if(fa[c[i]]&&lx[root[i]]>0) {
/// update_point(root[bl[pos[fa[c[i]]]]],pos[fa[c[i]]],a[fa[c[i]]]+lx[root[i]]);
// }
// }
// for(int i=1;i<=rt;++i) {
// printf(" %d\n",lx[root[i]]);
// }
/* int x,y; x=3; y=0;
printf("%d %d %d\n",mx[root[bl[pos[x]]]],lx[root[bl[pos[x]]]],rx[root[bl[pos[x]]]]);
update_point(root[bl[pos[x]]],pos[x],y);
Query(root[bl[pos[x]]],pos[x]);
cout<<mx[zz]<<" "<<lx[zz]<<" "<<rx[zz]<<endl;
addtion(root[bl[pos[x]]],pos[x],y-a[x]);
a[x]=y;
printf("%d %d %d\n",mx[root[bl[pos[x]]]],lx[root[bl[pos[x]]]],rx[root[bl[pos[x]]]]);*/
for(int i=1;i<=m;++i) {
int opt; read(opt);
if(opt==1) {
int x,y; read(x); read(y);
int cl=lx[root[bl[pos[x]]]];
// cout<<c<<endl;
addtion(root[bl[pos[x]]],pos[x],y-a[x]);
// cout<<mx[root[bl[pos[x]]]]<<endl;
// cout<<son[1]<<endl;
// cout<<top[x]<<endl;
// cout<<bl[pos[x]]<<endl;
update_point1(1,bl[pos[x]],mx[root[bl[pos[x]]]]);
a[x]=y;
// update_point(root[bl[pos[x]]],pos[x],y);
solve(x,cl);
continue;
}
if(opt==2) {
printf("%d\n",max(0,ma[1]));
continue;
}
}
return 0;
}