[BJOI 2017]木の難題

従来の考え方に従って、1つの点xを分治中心として選択し、xをサブツリーの各点への経路につなぐ.つなぎ合わせるときの2つのセグメントのインタフェース(すなわちxがつながっているエッジについて、ない場合は0番のエッジに設定します:色は0、長さは0、0番の息子に達します)の色の影響は、各セグメントのパス権値、辺数、およびそのセグメントのインタフェースを記録し、すべてのパスをインタフェースの色を第1のキーワードとし、インタフェース番号を第2のキーワードとしてソートすることができます.同じインタフェースに対するパスは、連続したシーケンスである必要があることは明らかである.このように各パスを列挙し、前に現れたエッジ数と要求に合致する最大のパス権値を見つければよい.2つのセグメントツリーでメンテナンスし、1つのメンテナンスはこのパスとは異なる色で、1つのメンテナンスはこのパスと同じ色ですが、インタフェースが異なる(単純なパスの接合は2つのエンドポイントが同じサブツリー内にないことを満たすため).
時間複雑度O(nlognlogn)
定数は巨大で、酸素吸入とc++11が必要です.

#include 
using namespace std;
const int N=2e5+10;
const int M=4e5+10;
const int inf=0x3f3f3f3f;

int n,m,L,R;
int c[N],head[N],to[M],clr[M],last[M];
int sum,top,rt,fiz[N],siz[N];
bool ban[N];

struct Seg {
    int dis,num,bel;
} p[N];

struct Rmq {
    #define ls (x<<1)
    #define rs (x<<1|1)
    int val[N<<2];
    bool tag[N<<2];
    void clear() {
        val[1]=-inf;
        tag[1]=1;
    }
    void pushDown(int x) {
        val[ls]=-inf,tag[ls]=1;
        val[rs]=-inf,tag[rs]=1;
        tag[x]=0;
    }
    void modify(int x,int l,int r,int p,int w) {
        if(l==r) return void(val[x]=w);
        int mid=(l+r)>>1;
        val[x]=max(val[x],w);
        if(tag[x]) pushDown(x);
        if(p<=mid) modify(ls,l,mid,p,w);
        else modify(rs,mid+1,r,p,w);
    }
    int query(int x,int l,int r,int L,int R) {
        if(L<=l && r<=R) return val[x];
        int mid=(l+r)>>1, ret=-inf;
        if(tag[x]) return ret;
        if(L<=mid) ret=max(ret,query(ls,l,mid,L,R));
        if(mid

転載先:https://www.cnblogs.com/nosta/p/10230167.html