• 如果您觉得本站非常有看点，那么赶紧使用Ctrl+D 收藏吧

# P3714 [BJOI2017]树的难题 点分治+线段树合并

2周前 (01-13) 11次浏览

## 代码

``````#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#define rg register
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=4e5+5;
int h[maxn],tot=1,n,m,lef,rig,val[maxn];
struct asd{
int to,nxt,val;
}b[maxn];
void ad(rg int aa,rg int bb,rg int cc){
b[tot].to=bb;
b[tot].nxt=h[aa];
b[tot].val=cc;
h[aa]=tot++;
}
int siz[maxn],maxsiz[maxn],rt,totsiz;
bool vis[maxn];
void getroot(rg int now,rg int lat){
siz[now]=1,maxsiz[now]=0;
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(u==lat || vis[u]) continue;
getroot(u,now);
siz[now]+=siz[u];
maxsiz[now]=std::max(maxsiz[now],siz[u]);
}
maxsiz[now]=std::max(maxsiz[now],totsiz-siz[now]);
if(maxsiz[now]<maxsiz[rt]) rt=now;
}
struct trr{
int lch,rch,val;
trr(){
lch=rch=0;
val=-0x3f3f3f3f;//一定要初始化成无穷小
}
}tr[maxn*40];
int cnt,rt1,rt2,tp,ans=-0x3f3f3f3f;
void push_up(rg int da){
tr[da].val=std::max(tr[tr[da].lch].val,tr[tr[da].rch].val);
}
int xg(rg int da,rg int l,rg int r,rg int wz,rg int val){
if(!da){
da=++cnt;
tr[da].lch=tr[da].rch=0,tr[da].val=-0x3f3f3f3f;
}
if(l==r){
tr[da].val=std::max(tr[da].val,val);
return da;
}
rg int mids=(l+r)>>1;
if(wz<=mids) tr[da].lch=xg(tr[da].lch,l,mids,wz,val);
else tr[da].rch=xg(tr[da].rch,mids+1,r,wz,val);
push_up(da);
return da;
}
int bing(rg int aa,rg int bb,rg int l,rg int r){
if(!aa || !bb) return aa+bb;
if(l==r){
tr[aa].val=std::max(tr[aa].val,tr.val);
tr.val=-0x3f3f3f3f;
return aa;
}
rg int mids=(l+r)>>1;
tr[aa].lch=bing(tr[aa].lch,tr.lch,l,mids);
tr[aa].rch=bing(tr[aa].rch,tr.rch,mids+1,r);
push_up(aa);
return aa;
}
int cx(rg int da,rg int l,rg int r,rg int nl,rg int nr){
if(!da || l>r) return -0x3f3f3f3f;
if(l>=nl && r<=nr) return tr[da].val;
rg int mids=(l+r)>>1,nans=-0x3f3f3f3f;
if(nl<=mids) nans=std::max(nans,cx(tr[da].lch,l,mids,nl,nr));
if(nr>mids) nans=std::max(nans,cx(tr[da].rch,mids+1,r,nl,nr));
return nans;
}
struct jie{
int val,dep;
jie(){}
jie(rg int aa,rg int bb){
val=aa,dep=bb;
}
}sta[maxn];
bool cmp(rg jie aa,rg jie bb){
return aa.val>bb.val;
}
std::vector<jie> g[maxn];
void dfs(rg int now,rg int lat,rg int nval,rg int ndep,rg int latcol){
if(ndep>rig) return;
sta[++tp]=jie(nval,ndep);
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(u==lat || vis[u]) continue;
dfs(u,now,(latcol==b[i].val)?nval:nval+val[b[i].val],ndep+1,b[i].val);
}
}
void solve(rg int now){
vis[now]=1;
rt1=rt2=cnt=0;
rg int latcol=0,jud=0;
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(!vis[u]){
tp=jud=0;
dfs(u,now,val[b[i].val],1,b[i].val);
if(b[i].val==latcol) jud=1;
else {
rt1=bing(rt1,rt2,1,n);
rt2=0;
}
for(rg int j=1;j<=tp;j++){
if(jud) ans=std::max(ans,cx(rt2,1,n,std::max(1,lef-sta[j].dep),rig-sta[j].dep)+sta[j].val-val[latcol]);
ans=std::max(ans,cx(rt1,1,n,std::max(1,lef-sta[j].dep),rig-sta[j].dep)+sta[j].val);
if(sta[j].dep>=lef && sta[j].dep<=rig) ans=std::max(ans,sta[j].val);
}
for(rg int j=1;j<=tp;j++) rt2=xg(rt2,1,n,sta[j].dep,sta[j].val);
latcol=b[i].val;
}
}
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(!vis[u]){
totsiz=siz[u],rt=0;
getroot(u,now);
solve(rt);
}
}
}
int main(){
memset(h,-1,sizeof(h));
rg int aa,bb,cc;
for(rg int i=1;i<n;i++){
g[aa].push_back(jie(cc,bb)),g.push_back(jie(cc,aa));
}
for(rg int i=1;i<=n;i++) std::sort(g[i].begin(),g[i].end(),cmp);
for(rg int i=1;i<=n;i++){
for(rg int j=0;j<g[i].size();j++){