辺分治
178855 ワード
記事の目次 bzoj 2870.最長道路tree uoj 347.【WC 2018】チャネル [CTSC2018]暴力書き込み -------3.14 up----------
今日書きながら分治した時、このブログのトップ3のテンプレートが間違っていたことに気づきました.ゲットするrootの時はszより問題があります.
bzoj 2870.一番長い道路tree
どのようなものですか?もしドゥア側でテンプレートの問題を分けて、ポイントをつけてもいいです.
子供でもドゥアというのは、1本目の木の上で分割して、処分するたびにポイントを取り出して、2本目の木に虚木を建て、分治辺の左右を押して染めるということです.虚木の上ですべてのlcaを列挙して、このlcaの子木の中の点を第一本の木の中で直径を求めて、異なった色の直径で解答を更新します.直径はマージ可能です
どちらでもドゥアはサイドと聞いていますが、虚樹dpを分けながらもいいと思いますか?次に題解を見に行きましたが、神様たちは式子化すると言いました.(R x＋R y＋d＿i s(x,y)／2−d＿i s’(x,y)(Rux＋Ruy＋dis(x,y)／2−dis'(x,y)(Rx＋Ry＋dis(x,y)／2 dily)は、2番目の列挙しかできません.そして一番目の木に、サブツリーの中でポイントの距離が一番大きいかを尋ねます.チャンネルの問題を発見した合併直径は磁気負によらず、辺分治で距離の最大値を探すことを考えています.辺分木は二叉の木で、線分樹のように合併して分木することができます.ガチョウの書き方があまりにも優秀ではないので、空間がちょっと爆発します.
今日書きながら分治した時、このブログのトップ3のテンプレートが間違っていたことに気づきました.ゲットするrootの時はszより問題があります.
bzoj 2870.一番長い道路tree
どのようなものですか?もしドゥア側でテンプレートの問題を分けて、ポイントをつけてもいいです.
//Achen
#include
",ans);
//cerr<
Formylove;
}
子供でもドゥアというのは、1本目の木の上で分割して、処分するたびにポイントを取り出して、2本目の木に虚木を建て、分治辺の左右を押して染めるということです.虚木の上ですべてのlcaを列挙して、このlcaの子木の中の点を第一本の木の中で直径を求めて、異なった色の直径で解答を更新します.直径はマージ可能です
//Achen
#include
",x);
return x;
}
int l=dfn2[x],r=dfn2[y],k=0;
if(l>r) swap(l,r);
while(l+(1<<k)-1<=r) k++; if(k) k--;
int a=st[l][k],b=st[r-(1<<k)+1][k];
int rs=R[a]<=R[b]?a:b;
//printf("%d
",rs);
return rs;
}
int in(int a,int b) { return dfn[a]>=dfn[b]&&dfn[a]<dfn[b]+sz[b]; }
LL dis(int x,int y) { return H[x]+H[y]-2LL*H[lca(x-n,y-n)]; }
int tot;
void dfs2(int x,int fa) {
for(int i=fir[x];i;i=nxt[i]) if(to[i]!=fa) {
son[x].push_back(to[i]);
edge[x].push_back(val[i]);
dfs2(to[i],x);
}
}
void lik() {
For(i,1,n) {
R[i+n]=R[i]+1;
//f[i+n][0]=i;
//For(j,1,16) f[i+n][j]=f[f[i+n][j-1]][j-1];
add(i,i+n,0);
an[i]=ecnt-1;
}
}
void rebuild() {
dfs2(1,0);
tot=n;
For(x,1,n) fir[x]=0; ecnt=1;
For(x,1,tot) {
int szz=son[x].size();
if(szz<=2) {
For(i,0,szz-1)
add(x,son[x][i],edge[x][i]);
}
else {
int t1=++tot,t2=++tot;
add(x,t1,0); add(x,t2,0);
For(i,0,szz-1) {
if(i&1) {
son[t1].push_back(son[x][i]);
edge[t1].push_back(edge[x][i]);
}
else {
son[t2].push_back(son[x][i]);
edge[t2].push_back(edge[x][i]);
}
}
}
}
}
}G[3];
int tim;
struct XUT {
int ecnt,fir[N],nxt[N<<1],to[N<<1],tag[N];
LL g[N][2][2],mx[N][2],tpans;
void add(int u,int v) {
nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v; //val[ecnt]=w;
//nxt[++ecnt]=fir[v]; fir[v]=ecnt; to[ecnt]=u; val[ecnt]=w;
}
void merge(int x,int y) {
For(a,0,1) For(b,0,1) {
if(g[x][0][a]&&g[y][1][b]) tpans=max(tpans,G[1].dis(g[x][0][a]+n,g[y][1][b]+n)-2LL*G[0].H[x]);
if(g[x][1][a]&&g[y][0][b]) tpans=max(tpans,G[1].dis(g[x][1][a]+n,g[y][0][b]+n)-2LL*G[0].H[x]);
}
For(i,0,1) {
int a=g[x][i][0],b=g[x][i][1]; LL mxx=mx[x][i];
if(!a||mxx<mx[y][i]) a=g[y][i][0],b=g[y][i][1],mxx=mx[y][i];
For(u,0,1) if(g[x][i][u]) For(v,0,1) if(g[y][i][v]){
LL tpp=G[1].dis(g[x][i][u]+n,g[y][i][v]+n);
if(!a||tpp>mxx) {
a=g[x][i][u]; b=g[y][i][v]; mxx=tpp;
}
}
g[x][i][0]=a; g[x][i][1]=b; mx[x][i]=mxx;
}
}
void dfs(int x) {
memset(g[x],0,sizeof(g[x])); mx[x][0]=mx[x][1]=mx[x][2]=0;
if(tag[x]==tim+1) g[x][0][0]=g[x][0][1]=x;
else if(tag[x]==tim+2) g[x][1][0]=g[x][1][1]=x;
for(int i=fir[x];i;i=nxt[i]) {
dfs(to[i]);
merge(x,to[i]);
}
}
LL solve() {
tpans=0;
dfs(1);
return tpans;
}
}X;
bool cmp(const int &A,const int &B) { return G[0].dfn[A]<G[0].dfn[B]; }
struct sol {
int sz[N],mxson[N],rt,nowsz,eg,vis[N];
void get_rt(int x,int fa,int SZ) {
sz[x]=1;
for(int i=G[2].fir[x];i;i=G[2].nxt[i]) {
int y=G[2].to[i];
if(y==fa||vis[i>>1]) continue;
get_rt(y,x,SZ);
sz[x]+=sz[y];
if(!rt||mxson[y]<nowsz) {
rt=x; nowsz=mxson[y]; eg=i;
}
}
mxson[x]=max(sz[x],SZ-sz[x]);
}
int sta[N],top;
LL R[N];
void dfs(int x,int fa,int tg) {
X.tag[x]=tg;
if(!fa) R[x]=0;
if(x<=n) {
sta[++top]=x;
G[1].val[G[1].an[x]]=R[x]+G[0].H[x];
G[1].H[x+n]=G[1].H[x]+R[x]+G[0].H[x];
G[1].val[G[1].an[x]+1]=R[x]+G[0].H[x];
}
for(int i=G[2].fir[x];i;i=G[2].nxt[i]) {
int y=G[2].to[i];
if(y==fa||vis[i>>1]) continue;
R[y]=R[x]+G[2].val[i];
dfs(y,x,tg);
}
}
int sta2[N],top2;
LL work() {
sort(sta+1,sta+top+1,cmp);
int up=top-1;
For(i,1,up) sta[++top]=G[0].lca(sta[i],sta[i+1]);
sta[++top]=1;
sort(sta+1,sta+top+1,cmp);
up=unique(sta+1,sta+top+1)-(sta+1);
For(i,1,up) X.fir[sta[i]]=0; X.ecnt=0;
top2=0;
For(i,1,up) {
while(top2&&!G[0].in(sta[i],sta2[top2])) top2--;
if(top2) X.add(sta2[top2],sta[i]);
sta2[++top2]=sta[i];
}
return X.solve();
}
void solve(int x,int SZ) {
rt=0;
get_rt(x,0,SZ);
if(!rt) return ;
vis[eg>>1]=1;
x=rt; int y=G[2].to[eg];
top=0;
dfs(x,0,tim+1); dfs(y,0,tim+2);
ans=max(ans,G[2].val[eg]+work());
tim+=2;
solve(x,SZ-sz[y]); solve(y,sz[y]);
}
}S;
int main() {
//freopen("rand.txt","r",stdin);
read(n);
For(o,0,2) For(i,2,n) {
int x,y; LL w;
read(x); read(y); read(w);
G[o].add(x,y,w);
}
G[0].dfs1(1,0);
G[0].make_st();
G[1].dfs1(1,0);
G[1].make_st();
G[1].lik();
G[2].rebuild();
S.solve(1,G[2].tot);
printf("%lld
",ans);
Formylove;
}
どちらでもドゥアはサイドと聞いていますが、虚樹dpを分けながらもいいと思いますか?次に題解を見に行きましたが、神様たちは式子化すると言いました.(R x＋R y＋d＿i s(x,y)／2−d＿i s’(x,y)(Rux＋Ruy＋dis(x,y)／2−dis'(x,y)(Rx＋Ry＋dis(x,y)／2 dily)は、2番目の列挙しかできません.そして一番目の木に、サブツリーの中でポイントの距離が一番大きいかを尋ねます.チャンネルの問題を発見した合併直径は磁気負によらず、辺分治で距離の最大値を探すことを考えています.辺分木は二叉の木で、線分樹のように合併して分木することができます.ガチョウの書き方があまりにも優秀ではないので、空間がちょっと爆発します.
//Achen
#include
",ans);
Formylove;
}