边分治
「BZOJ 2870」最长道路tree
点击查看代码
#include
using namespace std;
int n,m;
int v[400005];
int ver[400005],ne[400005],head[400005],cnt=1,val[400005];
inline void link(int x,int y,int v){
ver[++cnt]=y;
ne[cnt]=head[x];
head[x]=cnt;val[cnt]=v;
}
vector son[200005];
void init(int x,int fi){
for(int i=head[x];i;i=ne[i]){
int u=ver[i];
if(u==fi)continue;
init(u,x);son[x].push_back(u);
}
}
inline void build(){
init(1,1);
for(int i=1;i<=n;i++)head[i]=0;cnt=1;
for(int i=1;i<=m;i++){
if(son[i].size()<3){
for(auto it:son[i]){
link(i,it,it<=n);link(it,i,it<=n);
}
}
else{
int le=++m,ri=++m;v[le]=v[ri]=v[i];
link(i,le,0);link(le,i,0);
link(i,ri,0);link(ri,i,0);
for(auto it:son[i])son[le].push_back(it),swap(le,ri);
}
}
}
int siz[200005],mxp[400005],rt;
bool vis[400005];
void findrt(int x,int fi,int tot){
siz[x]=1;
for(int i=head[x];i;i=ne[i]){
int u=ver[i];
if(vis[i]||u==fi)continue;
findrt(u,x,tot);siz[x]+=siz[u];
mxp[i>>1]=max(siz[u],tot-siz[u]);
if(mxp[rt]>mxp[i>>1])rt=(i>>1);
}
}
void dfs(int x,int fi,int mn,int dep,vector >&vec){
mn=min(mn,v[x]);
vec.push_back(make_pair(mn,dep));
for(int i=head[x];i;i=ne[i]){
int u=ver[i];
if(vis[i]||u==fi)continue;
dfs(u,x,mn,dep+val[i],vec);
}
}
long long ans;
void solve(int x){
mxp[rt=0]=n;findrt(x,x,siz[x]);
if(!rt)return ;
vis[rt<<1]=vis[rt<<1|1]=1;
int L=ver[rt<<1],R=ver[rt<<1|1];
vector >le,ri;
dfs(L,R,1e9,val[rt<<1],le);dfs(R,L,1e9,1,ri);
sort(le.begin(),le.end());reverse(le.begin(),le.end());
sort(ri.begin(),ri.end());reverse(ri.begin(),ri.end());
auto it1=le.begin();
int lenl=0,lenr=0;
for(auto it2:ri){
while(it1!=le.end()&&it1->first>=it2.first){
ans=max(ans,1ll*it1->first*(lenr+it1->second));
lenl=max(lenl,it1->second);it1++;
}
ans=max(ans,1ll*it2.first*(lenl+it2.second));
lenr=max(lenr,it2.second);
}
solve(L);solve(R);
}
int main(){
scanf("%d",&n);m=n;
memset(v,0x3f,sizeof(v));
for(int i=1;i<=n;i++)scanf("%d",&v[i]);
for(int i=1;i
「WC2010」重建计划
点击查看代码
#include
using namespace std;
int n,m;
int Lim,U;
int ver[400005],ne[400005],head[400005],cnt,val[400005];
inline void link(int x,int y,int v){
ver[++cnt]=y;
ne[cnt]=head[x];
head[x]=cnt;val[cnt]=v;
}
vector son[400005];
int pre[400005];
void init(int x,int fi){
for(int i=head[x];i;i=ne[i]){
int u=ver[i];
if(u==fi)continue;
pre[u]=val[i];
init(u,x);son[x].push_back(u);
}
}
inline void build(){
init(1,1);m=n;
for(int i=1;i<=n;i++)head[i]=0;cnt=1;
for(int i=1;i<=m;i++){
if(son[i].size()<3){
for(auto it:son[i])link(it,i,pre[it]),link(i,it,pre[it]);
}
else {
int le=++m,ri=++m;
link(i,le,0);link(le,i,0);
link(i,ri,0);link(ri,i,0);
for(auto it:son[i])son[le].push_back(it),swap(le,ri);
}
}
}
bool vis[400005];
int siz[400005],mxp[400005],rt;
void findrt(int x,int fi,int tot){
siz[x]=1;
for(int i=head[x];i;i=ne[i]){
int u=ver[i];
if(vis[i]||u==fi)continue;
findrt(u,x,tot);siz[x]+=siz[u];mxp[i>>1]=max(siz[u],tot-siz[u]);
if(mxp[i>>1]>1);
}
}
vector le,ri;
double mid,res;
void dfs(int x,int fi,int dep,double len,vector&vec,bool is=0){
if(is){
if(vec.size()<=dep)vec.push_back(len);
else vec[dep]=max(vec[dep],len);
}siz[x]=1;
for(int i=head[x];i;i=ne[i]){
int u=ver[i];
if(vis[i]||u==fi)continue;
dfs(u,x,dep+(val[i]!=0),len+val[i]-mid*(val[i]!=0),vec,is|(val[i]!=0));
siz[x]+=siz[u];
}
}
pair que[400005];
int top,ed;
void solve(int x,int tot){
mxp[rt=0]=m;findrt(x,x,tot);
if(!rt)return ;vis[rt<<1]=vis[rt<<1|1]=1;
int L=ver[rt<<1],R=ver[rt<<1|1];
le.clear();ri.clear();
dfs(L,R,0,0,le,1);dfs(R,L,(val[rt<<1]!=0)-1,val[rt<<1]-mid*(val[rt<<1]!=0),ri,(val[rt<<1]!=0));
top=1;ed=0;
for(int i=0,j=le.size()-1;i=0&&i+j+1>=Lim){
while(top<=ed&&que[ed].firstU)top++;
if(top<=ed)res=max(res,ri[i]+que[top].first);
}
solve(L,siz[L]);solve(R,siz[R]);
}
inline bool check(){
for(int i=1;i<=cnt;i++)vis[i]=0;res=-1e9;
solve(1,m);return res>=0;
}
int main(){
scanf("%d",&n);
scanf("%d%d",&Lim,&U);
for(int i=1;i
边分树
「PA2019」Podatki drogowe
点击查看代码
#include
using namespace std;
int n,m,lim;long long k;
vector rt1[400005],rt2[400005];
namespace Main{
int le[10000005],ri[10000005],siz[10000005],cnt;
unsigned long long tree[10000005],val[100005];
int insert(int loc,int y,int l=1,int r=n){
if(locr)return y;
int i=++cnt;tree[i]=tree[y]+val[loc];siz[i]=siz[y]+1;
if(l!=r){
int mid=(l+r)>>1;
le[i]=insert(loc,le[y],l,mid);ri[i]=insert(loc,ri[y],mid+1,r);
}
return i;
}
inline bool cmp(int a,int b,int c,int d){
int l=1,r=n;
while(l!=r){
int mid=(l+r)>>1;
if(tree[ri[a]]+tree[ri[b]]!=tree[ri[c]]+tree[ri[d]]){
l=mid+1;
a=ri[a];b=ri[b];c=ri[c];d=ri[d];
}else {
r=mid;
a=le[a];b=le[b];c=le[c];d=le[d];
}
}
return siz[a]+siz[b] L[400005],R[400005],pos[400005];
struct node{
int x,y;
node(int _x,int _y){
x=_x;y=_y;
}
inline bool operator <(const node &b)const{
return cmp(x,y,b.x,b.y);
}
};
long long ans,base=1;
const long long md=1e9+7;
void Get(int x,int y,int l=1,int r=n){
if(l==r){
base=base*n%md;ans=(ans+(siz[x]+siz[y])*base)%md;
return ;
}
int mid=(l+r)>>1;
Get(le[x],le[y],l,mid);Get(ri[x],ri[y],mid+1,r);
}
inline void main(){
long long all=0;
for(int i=1;i<=lim;i++){
L[i].resize(rt1[i].size());R[i].resize(rt1[i].size());pos[i].resize(rt1[i].size());
for(auto &it:R[i])it=rt2[i].size()-1;all+=1ll*rt1[i].size()*rt2[i].size();
}
node mid(0,0);
for(int t=1;t<=60;t++){
long long rk=abs(1ll*rand()*rand()+rand())%all+1;
for(int i=1;rk&&i<=lim;i++){
for(int j=0;j=rk){
mid=node(rt1[i][j],rt2[i][L[i][j]+rk-1]);
rk=0;break;
}else rk-=tmp;
}
}
long long tmp=0;
for(int i=1;i<=lim;i++){
int r=rt2[i].size()-1;
for(int j=0;j=L[i][j]&&mid > son[100005];
int las[100005];
void init(int x,int fi){
for(auto it:son[x]){
int u=it.first;if(u==fi)continue;
init(u,x);
if(!las[x])link(x,u,it.second),link(u,x,it.second),las[x]=x;
else {
link(las[x],++m,0);link(m,las[x],0);las[x]=m;
link(las[x],u,it.second);link(u,las[x],it.second);
}
}
}
int siz[200005],mxp[200005],root;
bool vis[400005];
void findrt(int x,int fi,int tot){
siz[x]=1;
for(int i=head[x];i;i=ne[i]){
int u=ver[i];if(vis[i]||u==fi)continue;
findrt(u,x,tot);siz[x]+=siz[u];mxp[i>>1]=max(tot-siz[u],siz[u]);
if(mxp[root]>mxp[i>>1])root=(i>>1);
}
}
int rt[200005];
vector vec;
void dfs(int x,int fi){
if(x<=n)vec.push_back(rt[x]);
siz[x]=1;
for(int i=head[x];i;i=ne[i]){
int u=ver[i];
if(vis[i]||u==fi)continue;
rt[u]=Main::insert(val[i],rt[x]);
dfs(u,x);siz[x]+=siz[u];
}
}
void solve(int x,int tot){
mxp[root=0]=m;findrt(x,x,tot);
if(!root)return ;vis[root<<1]=vis[root<<1|1]=1;
int L=ver[root<<1],R=ver[root<<1|1];++lim;
rt[L]=0;vec.clear();dfs(L,R);
sort(vec.begin(),vec.end(),Main::ccmp);swap(rt1[lim],vec);
rt[R]=Main::insert(val[root<<1],0);vec.clear();dfs(R,L);
sort(vec.begin(),vec.end(),Main::ccmp);swap(rt2[lim],vec);
solve(L,siz[L]);solve(R,siz[R]);
}
inline void main(){
for(int i=1;i<=n;i++)Main::val[i]=1ll*rand()*rand()*rand()+1ll*rand()*rand()+rand();
for(int i=1;i
CF757G Can Bash Save the Day?
点击查看代码
#include
using namespace std;
int n,m,q;
int ver[800005],ne[800005],head[400005],cnt=1;
long long val[800005];
inline void link(int x,int y,long long v){
ver[++cnt]=y;
ne[cnt]=head[x];
head[x]=cnt;val[cnt]=v;
}
vector son[800005];
long long fa[200005];
void init(int x,int fi){
for(int i=head[x];i;i=ne[i]){
int u=ver[i];
if(u==fi)continue;
fa[u]=val[i];
init(u,x);son[x].push_back(u);
}
}
inline void build(){
init(1,1);m=n;
for(int i=1;i<=n;i++)head[i]=0;cnt=1;
for(int i=1;i<=m;i++){
if(son[i].size()<3){
for(auto it:son[i])link(i,it,fa[it]),link(it,i,fa[it]);
}else {
int le=++m,ri=++m;
link(i,le,0);link(le,i,0);
link(i,ri,0);link(ri,i,0);
for(auto it:son[i])son[le].push_back(it),swap(le,ri);
}
}
}
int siz[400005],mxp[800005],rt;
bool vis[800005];
void findrt(int x,int fi,int tot){
siz[x]=1;
for(int i=head[x];i;i=ne[i]){
int u=ver[i];
if(vis[i]||u==fi)continue;
findrt(u,x,tot);siz[x]+=siz[u];
mxp[i>>1]=max(tot-siz[u],siz[u]);
// cout<"<>1]<mxp[i>>1])rt=(i>>1);
}
// cout< vec;
long long dep[400005];
void dfs(int x,int fi){
vec.push_back(x);
for(int i=head[x];i;i=ne[i]){
int u=ver[i];
if(vis[i]||u==fi)continue;
dep[u]=dep[x]+val[i];
dfs(u,x);
}
}
int le[12000005],ri[12000005],root[200005],lst[200005],all;
long long tree[12000005],sum[12000005];
void solve(int x){
mxp[rt=0]=n;findrt(x,x,siz[x]);
if(!rt)return ;vis[rt<<1]=vis[rt<<1|1]=1;
int L=ver[rt<<1],R=ver[rt<<1|1];
// cout<<"solve "<n)continue;
le[lst[it]]=++all;lst[it]=all;
tree[lst[it]]=dep[it];
}
vec.clear();dep[R]=0;dfs(R,L);
for(auto it:vec){
if(it>n)continue;
ri[lst[it]]=++all;lst[it]=all;
tree[lst[it]]=dep[it];
}
solve(L);solve(R);
}
int merge(int a,int b){
if(!a||!b)return a+b;
int i=++all;tree[i]=tree[a]+tree[b];sum[i]=sum[a]+sum[b];
le[i]=merge(le[a],le[b]);
ri[i]=merge(ri[a],ri[b]);
return i;
}
long long query(int x,int y){
// cout<
「GYM 102391」K. Wind of Change
点击查看代码
#include
using namespace std;
int n;
namespace T1{
int rt[1000005],le[50000005],ri[50000005],all;
long long tree[50000005],dep[1000005],ans[1000005];
inline void insert(int x,int y){
int now=rt[x];
while(1){
if(le[now]){
if(!le[y])le[y]=++all,tree[all]=1e18;
tree[le[y]]=min(tree[le[y]],tree[le[now]]+dep[x]);
now=le[now];y=le[y];
}else if(ri[now]){
if(!ri[y])ri[y]=++all,tree[all]=1e18;
tree[ri[y]]=min(tree[ri[y]],tree[ri[now]]+dep[x]);
now=ri[now];y=ri[y];
}else break;
}
}
inline void del(){
tree[all]=1e18;le[all]=ri[all]=0;all--;
}
inline long long query(int x,int y){
int now=rt[x];long long res=1e18;
while(1){
if(le[now]){
res=min(res,tree[le[now]]+dep[x]+tree[ri[y]]);
now=le[now];y=le[y];
}else if(ri[now]){
res=min(res,tree[ri[now]]+dep[x]+tree[le[y]]);
now=ri[now];y=ri[y];
}else break;
}
return res;
}
inline void calc(vector &le,vector &ri){
int tmp=all,rtl=++all,rtr=++all;
for(auto it:le)insert(it,rtl);
for(auto it:ri)insert(it,rtr);
for(auto it:le)ans[it]=min(ans[it],query(it,rtr));
for(auto it:ri)ans[it]=min(ans[it],query(it,rtl));
while(all>tmp)del();
}
int m;
int ver[2000005],ne[2000005],head[1000005],cnt,val[2000005];
inline void link(int x,int y,int v){
ver[++cnt]=y;
ne[cnt]=head[x];
head[x]=cnt;val[cnt]=v;
}
vector son[1000005];
int fa[1000005];
void init(int x,int fi){
for(int i=head[x];i;i=ne[i]){
int u=ver[i];
if(u==fi)continue;
fa[u]=val[i];
init(u,x);son[x].push_back(u);
}
}
inline void build(){
init(1,1);cnt=1;m=n;
for(int i=1;i<=n;i++)head[i]=0;
for(int i=1;i<=n;i++)ans[i]=1e18;
for(int i=1;i<=m;i++){
if(son[i].size()<3){
for(auto it:son[i])link(i,it,fa[it]),link(it,i,fa[it]);
}
else {
int le=++m,ri=++m;
link(i,le,0);link(le,i,0);
link(i,ri,0);link(ri,i,0);
for(auto it:son[i])son[le].push_back(it),swap(le,ri);
}
}
}
int siz[1000005],mxp[1000005],root;
bool vis[2000005];
void findrt(int x,int fi,int tot){
siz[x]=1;
for(int i=head[x];i;i=ne[i]){
int u=ver[i];
if(vis[i]||u==fi)continue;
findrt(u,x,tot);siz[x]+=siz[u];
mxp[i>>1]=max(tot-siz[u],siz[u]);
if(mxp[i>>1]>1);
}
}
vector vec;
void dfs(int x,int fi){
siz[x]=1;
for(int i=head[x];i;i=ne[i]){
int u=ver[i];
if(vis[i]||u==fi)continue;
dep[u]=dep[x]+val[i];dfs(u,x);siz[x]+=siz[u];
}if(x<=n)vec.push_back(x);
}
void solve(int x,int tot){
mxp[root=0]=m;findrt(x,x,tot);
if(!root)return ;vis[root<<1]=vis[root<<1|1]=1;
int L=ver[root<<1],R=ver[root<<1|1];
vec.clear();dep[L]=0;dfs(L,R);
vector le;swap(le,vec);
vec.clear();dep[R]=val[root<<1];dfs(R,L);calc(le,vec);
solve(L,siz[L]);solve(R,siz[R]);
}
inline void main(){
tree[0]=1e18;
for(int i=1;i son[2000005];
int fa[2000005],lst[1000005];
void init(int x,int fi){
for(int i=head[x];i;i=ne[i]){
int u=ver[i];
if(u==fi)continue;
fa[u]=val[i];
init(u,x);son[x].push_back(u);
}
}
inline void build(){
init(1,1);cnt=1;m=n;
for(int i=1;i<=n;i++)head[i]=0;
for(int i=1;i<=n;i++)T1::rt[i]=lst[i]=++T1::all;
for(int i=1;i<=m;i++){
if(son[i].size()<3){
for(auto it:son[i])link(i,it,fa[it]),link(it,i,fa[it]);
}
else {
int le=++m,ri=++m;
link(i,le,0);link(le,i,0);
link(i,ri,0);link(ri,i,0);
for(auto it:son[i])son[le].push_back(it),swap(le,ri);
}
}
}
int siz[1000005],mxp[1000005],rt;
bool vis[2000005];
void findrt(int x,int fi,int tot){
siz[x]=1;
for(int i=head[x];i;i=ne[i]){
int u=ver[i];
if(vis[i]||u==fi)continue;
findrt(u,x,tot);siz[x]+=siz[u];
mxp[i>>1]=max(tot-siz[u],siz[u]);
if(mxp[i>>1]>1);
}
}
long long dep[1000005];
vector vec;
void dfs(int x,int fi){
siz[x]=1;
for(int i=head[x];i;i=ne[i]){
int u=ver[i];
if(vis[i]||u==fi)continue;
dep[u]=dep[x]+val[i];dfs(u,x);siz[x]+=siz[u];
}if(x<=n)vec.push_back(x);
}
void solve(int x,int tot){
mxp[rt=0]=m;findrt(x,x,tot);
if(!rt)return ;vis[rt<<1]=vis[rt<<1|1]=1;
int L=ver[rt<<1],R=ver[rt<<1|1];
vec.clear();dep[L]=0;dfs(L,R);
for(auto it:vec){
T1::le[lst[it]]=++T1::all;lst[it]=T1::all;
T1::tree[lst[it]]=dep[it];
}
vec.clear();dep[R]=val[rt<<1];dfs(R,L);
for(auto it:vec){
T1::ri[lst[it]]=++T1::all;lst[it]=T1::all;
T1::tree[lst[it]]=dep[it];
}solve(L,siz[L]);solve(R,siz[R]);
}
inline void main(){
for(int i=1;i
「CTSC2018」暴力写挂
点击查看代码
#include
using namespace std;
#define int long long
int n,m;
int ans;
namespace T2{
int rt[800005],tree[80000005],le[80000005],ri[80000005],all;
int dep[800005];
int merge(int a,int b,int &res){
if(!a||!b)return a+b;
if(le[a]&&ri[b])res=max(res,tree[le[a]]+tree[ri[b]]);
if(ri[a]&&le[b])res=max(res,tree[ri[a]]+tree[le[b]]);
le[a]=merge(le[a],le[b],res);
ri[a]=merge(ri[a],ri[b],res);tree[a]=max(tree[a],tree[b]);
return a;
}
int ver[800005],ne[800005],head[800005],cnt,val[800005];
inline void link(int x,int y,int v){
ver[++cnt]=y;
ne[cnt]=head[x];
head[x]=cnt;val[cnt]=v;
}
void dfs(int x,int fi){
int res=-1e18;
for(int i=head[x];i;i=ne[i]){
int u=ver[i];
if(u==fi)continue;
dep[u]=dep[x]+val[i];
dfs(u,x);rt[x]=merge(rt[x],rt[u],res);
}
ans=max(ans,res-2*dep[x]);
}
}
namespace T1{
int ver[1600005],ne[1600005],head[1600005],cnt=1,val[1600005];
inline void link(int x,int y,int v){
ver[++cnt]=y;
ne[cnt]=head[x];
head[x]=cnt;val[cnt]=v;
}
int dep[800005],fa[800005];
vector son[800005];
void init(int x,int fi){
for(int i=head[x];i;i=ne[i]){
int u=ver[i];
if(u==fi)continue;
dep[u]=dep[x]+val[i];fa[u]=val[i];
init(u,x);son[x].push_back(u);
}
}
inline void build(){
init(1,1);m=n;
for(int i=1;i<=n;i++)head[i]=0;cnt=1;
for(int i=1;i<=m;i++){
if(son[i].size()<3){
for(auto it:son[i]){
link(i,it,fa[it]);link(it,i,fa[it]);
}
}else {
int le=++m,ri=++m;
link(i,le,0);link(le,i,0);
link(i,ri,0);link(ri,i,0);
for(auto it:son[i])son[le].push_back(it),swap(le,ri);
}
}
}
int siz[800005],mxp[800005],rt;
bool vis[1600005];
void findrt(int x,int fi,int tot){
siz[x]=1;
for(int i=head[x];i;i=ne[i]){
int u=ver[i];
if(vis[i]||u==fi)continue;
findrt(u,x,tot);siz[x]+=siz[u];
mxp[i>>1]=max(siz[u],tot-siz[u]);
if(mxp[i>>1]>1);
}
}
int dis[800005],lst[800005];
vector vec;
void dfs(int x,int fi){
vec.push_back(x);siz[x]=1;
for(int i=head[x];i;i=ne[i]){
int u=ver[i];
if(vis[i]||u==fi)continue;
dis[u]=dis[x]+val[i];
dfs(u,x);siz[x]+=siz[u];
}
}
void solve(int x){
mxp[rt=0]=n;findrt(x,x,siz[x]);
if(!rt)return ;vis[rt<<1]=vis[rt<<1|1]=1;
int L=ver[rt<<1],R=ver[rt<<1|1];
vec.clear();dis[L]=val[rt<<1];dfs(L,R);
for(auto it:vec){
if(it>n)continue;
T2::le[lst[it]]=++T2::all;lst[it]=T2::all;
T2::tree[lst[it]]=dis[it]+dep[it];
}
vec.clear();dis[R]=0;dfs(R,L);
for(auto it:vec){
if(it>n)continue;
T2::ri[lst[it]]=++T2::all;lst[it]=T2::all;
T2::tree[lst[it]]=dis[it]+dep[it];
}
solve(L);solve(R);
}
}
signed main(){
scanf("%lld",&n);
for(int i=1;i
「WC2018」通道
点击查看代码
#include
using namespace std;
int n;
struct Tree{
int ver[200005],ne[200005],head[200005],cnt;
long long val[200005];
inline void link(int x,int y,long long v){
ver[++cnt]=y;
ne[cnt]=head[x];
head[x]=cnt;val[cnt]=v;
}
long long dep[100005];
void dfs(int x,int fi){
for(int i=head[x];i;i=ne[i]){
int u=ver[i];
if(u==fi)continue;
dep[u]=dep[x]+val[i];
dfs(u,x);
}
}
Tree(){
for(int i=1;ires)res=tmp,nxt=i;
}x=nxt;if(vis[x])break;
}
}
printf("%lld",ans);
return 0;
}