LiChaoTreeを使ったの2回目かな?
https://codeforces.com/contest/1303/problem/G
問題
木を成す無向グラフが与えられる。
各点には整数値が設定されている。
あるパスを選んだ時、通過した点の設定値を並べた数列をSとする。
Sに対し、prefix sumを取って作った数列をf(S)とする。
sum(f(S))の最大値を求めよ。
解法
重心分解をしながら、重心cを通る2つのパスを選び、連結したパスにおけるf(S)の最大値を求めよう。
その際、その際片方、例えば前半分となるパスを選んだ時、後ろ半分を選ぶわけだが、その際後ろ半分の頂点数と、前半分の数値の総和の積が最終的なsum(f(S))に影響する。
これは結局たくさんある1次式の最大値を求める問題といえるので、Convex-Hull TrickかLiChaoTreeで最適なものを選ぶようにしよう。
int N; vector<int> E[201010]; int vis[201010]; int NV[201010]; ll A[202020]; ll ret=0; vector<pair<ll,ll>> V; template<typename V> struct LeChaoTree { static const V inf=3LL<<60; const ll range=1<<20; const bool cmptype=true; //true:max false:min struct node { node(V a=0,V b=-inf) : A(a),B(b){ le=ri=NULL;} V val(ll x) { return A*x+B;} V A,B; // Ax+B node *le, *ri; }; node* root; LeChaoTree() { root=new node(0,-inf);} void add(node* n, V a,V b,ll L,ll R) { ll M=(L+R)/2; bool lef=(n->val(L) > a*L+b); bool mid=(n->val(M) > a*M+b); bool ri=(n->val(R) > a*R+b); if(lef&&ri) return; if(!lef&&(!ri || R-L==1)) { n->A=a; n->B=b; return; } if(R-L==1) return; if(!n->ri) n->ri=new node(); if(!n->le) n->le=new node(); add(n->ri,a,b,M,R); add(n->le,a,b,L,M); } void add(V a,V b) { if(!cmptype) a=-a,b=-b; add(root,a,b,0,range); } V query(ll x) { V ret=-inf; node* cur=root; ll L=0, R=range; while(cur) { ret=max(ret,cur->val(x)); ll m=(L+R)/2; if(x<m) cur=cur->le, R=m; else cur=cur->ri, L=m; } if(!cmptype) ret=-ret; return ret; } }; LeChaoTree<ll>* lct; int dfs(int cur,int pre) { NV[cur]=1; FORR(e,E[cur]) if(e!=pre && vis[e]==0) NV[cur]+=dfs(e,cur); return NV[cur]; } int dfs2(int cur,int pre,int TNV) { int tot=1; int ok=1; FORR(e,E[cur]) if(e!=pre && vis[e]==0) { int c = dfs2(e,cur,TNV); if(c!=-1) return c; tot += NV[e]; if(NV[e]*2>TNV) ok=0; } if((TNV-tot)*2>TNV) ok=0; if(ok) return cur; return -1; } void dfs3(int cur,int pre,ll S,ll T,ll w,ll S2,ll T2,ll d) { T+=A[cur]; S+=++w*A[cur]; V.push_back({T,S}); T2+=A[cur]; S2+=T2; d++; //cout<<"!"<<cur<<" "<<S<<" "<<T<<" "<<w<<" "<<d<<" "<<S2<<" "<<T2<<" "<<lct->query(d)<<endl; ret=max(ret,lct->query(d)+S2); ret=max(ret,S); FORR(e,E[cur]) if(e!=pre && vis[e]==0) dfs3(e,cur,S,T,w,S2,T2,d); } void split(int cur) { int TNV = dfs(cur,-1); if(TNV==0) return; int center=dfs2(cur,-1,TNV); //cout<<"go"<<center<<endl; lct=new LeChaoTree<ll>(); lct->add(A[center],A[center]); FORR(e,E[center]) if(vis[e]==0) { dfs3(e,center,A[center],A[center],1,0,0,0); FORR(v,V) lct->add(v.first,v.second); V.clear(); } reverse(ALL(E[center])); lct=new LeChaoTree<ll>(); lct->add(A[center],A[center]); FORR(e,E[center]) if(vis[e]==0) { dfs3(e,center,A[center],A[center],1,0,0,0); FORR(v,V) lct->add(v.first,v.second); V.clear(); } vis[center]=1; FORR(e,E[center]) if(vis[e]==0) split(e); } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N-1) { cin>>x>>y; E[x-1].push_back(y-1); E[y-1].push_back(x-1); } FOR(i,N) cin>>A[i]; split(0); cout<<ret<<endl; }
まとめ
本番なんでCHT避けたんだろう。整数だけだったからかな。