Heavy-Light Decomposition + 遅延評価 Segment Tree (しかも、区間和、左端からの和の最大値、右端からの和の最大値、区間の中での連続する和の最大値の4種類を持たないといけない)。
めちゃくちゃ重いが、特に大きなバグなく通すことができvery good.
#include<stdio.h> #include<algorithm> #include<vector> #include<queue> #define BEGIN_STACK_EXTEND(size) void * stack_extend_memory_ = malloc(size);void * stack_extend_origin_memory_;char * stack_extend_dummy_memory_ = (char*)alloca((1+(int)(((long long)stack_extend_memory_)&127))*16);*stack_extend_dummy_memory_ = 0;asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp":"=b"(stack_extend_origin_memory_):"a"((char*)stack_extend_memory_+(size)-1024)); #define END_STACK_EXTEND asm volatile("mov %%rax, %%rsp"::"a"(stack_extend_origin_memory_));free(stack_extend_memory_); using namespace std; int c[210000]; int sz[210000]; int eu[410000]; int conv[210000]; int rev[210000]; vector<int>g[210000]; int L[210000]; int par[210000]; int str[210000]; int ww[210000]; int wn[210000]; int cur; int cur2; void dfs(int a,int b){ par[a]=b; conv[a]=cur; rev[cur]=a; cur++; L[a]=cur2; eu[cur2++]=a; sz[a]=1; str[a]=-1; for(int i=0;i<g[a].size();i++){ if(g[a][i]==b)continue; dfs(g[a][i],a); eu[cur2++]=a; sz[a]+=sz[g[a][i]]; if(str[a]==-1||sz[str[a]]<sz[g[a][i]]){ str[a]=g[a][i]; } } if(sz[str[a]]*2<sz[a])str[a]=-1; } // 0: sum // 1: left-max // 2: right-max // 3: max struct wolf{ vector<int> node; vector<long long>segtree[4]; vector<long long>lazy[4]; int par; int at; int n; wolf(){ par=at=-1; } }; int mod=1000000007; long long inf=(long long)mod*mod; vector<wolf> hl; void proc(int a,int b,int c,int d,int e,int node,int type){ long long f=hl[node].lazy[type][e]; hl[node].lazy[type][e*2]=hl[node].lazy[type][e*2+1]=hl[node].lazy[type][e]; hl[node].lazy[type][e]=mod; if(type==0){ hl[node].segtree[type][e*2]=hl[node].segtree[type][e*2+1]=hl[node].segtree[type][e]/2; }else{ if(f<0)hl[node].segtree[type][e*2]=hl[node].segtree[type][e*2+1]=f; else hl[node].segtree[type][e*2]=hl[node].segtree[type][e*2+1]=hl[node].segtree[type][e]/2; } } void update(int a,int b,int c,int d,int e,long long f,int node,int type){ if(d<a||b<c)return; if(c<=a&&b<=d){ hl[node].lazy[type][e]=f; if(type==0){ hl[node].segtree[type][e]=f*(b-a+1); }else{ if(f<0)hl[node].segtree[type][e]=f; else hl[node].segtree[type][e]=f*(b-a+1); } return; } if(hl[node].lazy[type][e]!=mod){ proc(a,b,c,d,e,node,type); } update(a,(a+b)/2,c,d,e*2,f,node,type); update((a+b)/2+1,b,c,d,e*2+1,f,node,type); if(type==0){ hl[node].segtree[type][e]=hl[node].segtree[type][e*2]+hl[node].segtree[type][e*2+1]; }else if(type==1){ hl[node].segtree[type][e]=max(hl[node].segtree[1][e*2],hl[node].segtree[0][e*2]+hl[node].segtree[1][e*2+1]); }else if(type==2){ hl[node].segtree[type][e]=max(hl[node].segtree[2][e*2+1],hl[node].segtree[0][e*2+1]+hl[node].segtree[2][e*2]); }else{ hl[node].segtree[type][e]=max(max(hl[node].segtree[3][e*2],hl[node].segtree[3][e*2+1]),hl[node].segtree[2][e*2]+hl[node].segtree[1][e*2+1]); } } vector<long long> query(int a,int b,int c,int d,int e,int node){ // printf("%d %d %d %d %d %d\n",a,b,c,d,e,node); vector<long long>ret(4); if(d<a||b<c){ ret[0]=0;ret[1]=ret[2]=ret[3]=-inf;return ret; } if(c<=a&&b<=d){ for(int i=0;i<4;i++)ret[i]=hl[node].segtree[i][e]; return ret; } for(int i=0;i<4;i++){ if(hl[node].lazy[i][e]!=mod){ proc(a,b,c,d,e,node,i); } } vector<long long> left=query(a,(a+b)/2,c,d,e*2,node); vector<long long> right=query((a+b)/2+1,b,c,d,e*2+1,node); ret[0]=left[0]+right[0]; ret[1]=max(left[1],right[1]+left[0]); ret[2]=max(right[2],left[2]+right[0]); ret[3]=max(max(left[3],right[3]),left[2]+right[1]); return ret; } int lcaseg[1048576]; int lcaupd(int a,int b){ a+=524288; while(a){ lcaseg[a]=min(lcaseg[a],b); a/=2; } } int lcamin(int a,int b,int c,int d,int e){ if(d<a||b<c)return mod; if(c<=a&&b<=d)return lcaseg[e]; return min(lcamin(a,(a+b)/2,c,d,e*2),lcamin((a+b)/2+1,b,c,d,e*2+1)); } int main(){ BEGIN_STACK_EXTEND(250*1024*1024) int a,b; scanf("%d%d",&a,&b); for(int i=0;i<a;i++){ scanf("%d",c+i); } for(int i=0;i<a-1;i++){ int p,q; scanf("%d%d",&p,&q); p--;q--; g[p].push_back(q); g[q].push_back(p); } dfs(0,-1); hl.push_back(wolf()); hl[0].node.push_back(0); queue<pair<int,int> >Q; Q.push(make_pair(0,0)); ww[0]=wn[0]=0; while(Q.size()){ int at=Q.front().first; int seq=Q.front().second; Q.pop(); for(int i=0;i<g[at].size();i++){ if(g[at][i]==par[at])continue; if(str[at]==g[at][i]){ ww[g[at][i]]=seq; wn[g[at][i]]=hl[seq].node.size(); hl[seq].node.push_back(g[at][i]); Q.push(make_pair(g[at][i],seq)); }else{ Q.push(make_pair(g[at][i],hl.size())); ww[g[at][i]]=hl.size(); wn[g[at][i]]=0; hl.push_back(wolf()); hl[hl.size()-1].node.push_back(g[at][i]); hl[hl.size()-1].par=seq; hl[hl.size()-1].at=wn[at]; } } } for(int i=0;i<1048576;i++)lcaseg[i]=mod; for(int i=0;i<cur2;i++){ lcaupd(i,conv[eu[i]]); } for(int i=0;i<hl.size();i++){ hl[i].n=1; while(hl[i].n<hl[i].node.size())hl[i].n*=2; for(int j=0;j<4;j++){ hl[i].segtree[j]=vector<long long>(hl[i].n*2); hl[i].lazy[j]=vector<long long>(hl[i].n*2); } for(int j=0;j<hl[i].node.size();j++){ for(int k=0;k<4;k++){ update(0,hl[i].n-1,j,j,1,c[hl[i].node[j]],i,k); } } } while(b--){ int p,q,r,s; scanf("%d%d%d%d",&p,&q,&r,&s); q--;r--; if(L[q]>L[r])swap(q,r); int lca=rev[lcamin(0,524287,L[q],L[r],1)]; int goal=ww[lca]; vector<pair<int,pair<int,int> > >ql; vector<pair<int,pair<int,int> > >qr; if(goal==ww[q]){ ql.push_back(make_pair(goal,make_pair(wn[q],wn[lca]))); }else{ ql.push_back(make_pair(ww[q],make_pair(wn[q],0))); int now=hl[ww[q]].par; int at=hl[ww[q]].at; while(now!=goal){ ql.push_back(make_pair(now,make_pair(at,0))); at=hl[now].at; now=hl[now].par; } ql.push_back(make_pair(goal,make_pair(at,wn[lca]))); } if(goal==ww[r]){ if(r!=lca)qr.push_back(make_pair(goal,make_pair(wn[r],wn[lca]+1))); }else{ qr.push_back(make_pair(ww[r],make_pair(wn[r],0))); int now=hl[ww[r]].par; int at=hl[ww[r]].at; while(now!=goal){ qr.push_back(make_pair(now,make_pair(at,0))); at=hl[now].at; now=hl[now].par; } if(at!=wn[lca])qr.push_back(make_pair(goal,make_pair(at,wn[lca]+1))); } if(qr.size()){ for(int i=qr.size()-1;i>=0;i--){ swap(qr[i].second.first,qr[i].second.second); ql.push_back(qr[i]); } } // printf("\n"); // for(int i=0;i<ql.size();i++){ // printf("%d (%d, %d)\n",ql[i].first,ql[i].second.first,ql[i].second.second); // } if(p==1){ for(int i=0;i<ql.size();i++){ if(ql[i].second.first>ql[i].second.second)swap(ql[i].second.first,ql[i].second.second); for(int j=0;j<4;j++){ update(0,hl[ql[i].first].n-1,ql[i].second.first,ql[i].second.second,1,s,ql[i].first,j); } } }else{ long long ret=-inf; vector<long long>res[4]; for(int i=0;i<ql.size();i++){ vector<long long>t=query(0,hl[ql[i].first].n-1,min(ql[i].second.first,ql[i].second.second),max(ql[i].second.first,ql[i].second.second),1,ql[i].first); if(ql[i].second.first>ql[i].second.second)swap(t[1],t[2]); for(int j=0;j<4;j++)res[j].push_back(t[j]); } long long cur=-inf; for(int i=0;i<ql.size();i++){ // printf("%lld %lld %lld %lld\n",res[0][i],res[1][i],res[2][i],res[3][i]); ret=max(ret,res[3][i]); ret=max(ret,res[1][i]+cur); cur+=res[0][i]; cur=max(cur,res[2][i]); } printf("%lld\n",ret); } } /*for(int i=0;i<4;i++){ for(int j=0;j<hl[4].n*2;j++){ printf("%lld ",hl[4].segtree[i][j]); } printf("\n"); }*/ END_STACK_EXTEND }
