题解 P3250 【[HNOI2016]网络】

· · 题解

这是一道 提高+ 的题目。

题中求不经过某点的最大权路径，

考虑二分答案，问题转化为检验权>=mid的路径是否都经过某点,可以通过求>=mid的路径的交内是否包含某点来检验。

考虑线段树维护[l,r]权值区间内的所有路径的交。

那么合并的时候相当于两边的交求交，但是容易发现交都是一条线段或者一个点，所以就是求两条路径的交。

路径(a,b)与(c,d)的交，先求出p1 = lca(a,c) , p2 = lca(a,d) , p3 = lca(b,c) , p4= lca(b,d) 找出深度最大的两个点pm1,pm2。

只要这两个点pm1,pm2都在(a,b)与(c,d)上。

那么交就是(pm1,pm2)，反之则没有交。

可以利用如果pm1!=pm2则必有交来简化代码,可以用RMQLCA预处理做到O(1)。

那么我们就可以O(\log n)维护权值区间路径交,插入和删除只需要看做单点修改即可，但是权值相等的情况下不能看做单点修改，所以需要做一类把权值扩大的离散化。

此时我们可以做到O(n \log^2 n)

但是发现二分的过程可以在线段树上完成。

O(n\log n)

回顾一下我们用到的算法，线段树二分(NOIp2017D2T3)，树上路径求交的O(1)LCA实现（NOIp2015D2T3），我们可以轻松的得出这是一道提高+的题目。

但是囿于合并路径的常数(二位数)与复杂度不够优秀的非正解（整体二分+树状数组）的常数相比实在太大。

楼主现学了一发fwrite + zkw线段树才排到了非unshown的\texttt{rk1}，实在是惭愧于优秀的O(n\log n)的正解。

\texttt{AC Code:} 
#include<bits/stdc++.h>
#define maxn 200005
#define lim 19
#define lc u<<1
#define rc u<<1|1
#define mp make_pair
using namespace std;

char cb[1000000],*cs=cb,*ct=cb;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1000000,stdin),cs==ct)?0:*cs++)
void read(int &res){
    char ch;
    for(;!isdigit(ch=getc()););
    for(res=ch-'0';isdigit(ch=getc());res=res*10+ch-'0');
}
char wb[1000000],*wa=wb;

int n,m;
int info[maxn],Prev[maxn],to[maxn],cnt,cnt_e;
pair<int,int>sb[maxn];
void Node(int u,int v){ Prev[++cnt_e]=info[u],info[u]=cnt_e,to[cnt_e]=v; }
int dat[maxn][4],st[lim][maxn],lg[maxn],pos[maxn],tot,dep[maxn];

void dfs(int u,int ff){
    dep[u] = dep[ff] + 1;
    st[0][pos[u] = ++tot] = u;
    for(int i=info[u];i;i=Prev[i])
        if(to[i]!=ff){
            dfs(to[i],u);
            st[0][++tot] = u;
        }
}
inline int Lca(int u,int v){
    u = pos[u] , v = pos[v];
    if(u > v) swap(u,v);
    int t = lg[v-u+1];
    return dep[st[t][u]] < dep[st[t][v-(1<<t)+1]] ? st[t][u] : st[t][v-(1<<t)+1];
}

int pt[maxn<<2][2],M;
inline bool cmp(const int &u,const int &v){ return dep[u] > dep[v]; }
inline void merge(int *c,int *a,int *b){
    if(a[0] == -1 || b[0] == -1) c[0] = c[1] = -1;
    else if(!a[0] || !b[0]) c[0] = a[0] + b[0] , c[1] = a[1] + b[1];
    else{
        static int p[4] = {};
        p[0] = Lca(a[0],b[0]) , p[1] = Lca(a[1],b[1]) , p[2] = Lca(a[1],b[0]) , p[3] = Lca(a[0],b[1]);
        sort(p,p+4,cmp);
        if(p[0] != p[1]) c[0] = p[0] , c[1] = p[1];
        else if(p[0] == Lca(a[0],a[1]) || p[0] == Lca(b[0],b[1])) c[0] = c[1] = p[0] = p[1];
        else c[0] = c[1] = -1;
    }
}
inline bool chk(int u,int *p){
    if(p[0] == -1) return 0;
    if(p[0] == 0) return 1;
    if(dep[u] < dep[Lca(p[0],p[1])]) return 0;
    return Lca(u,p[0]) == u || Lca(u,p[1]) == u;
}
inline void Insert(int pos,int p1,int p2){
    pos += M - 1;
    for(pt[pos][0] = p1 , pt[pos][1] = p2;pos>1;pos>>=1)
        merge(pt[pos>>1],pt[pos],pt[pos^1]);
}
inline int solve(int u,int l,int r,int t){
    for(int mid;l<r;){
        mid = (l+r) >> 1;
        if(chk(t,pt[rc])) u=lc,r = mid;
        else u=rc,l = mid+1;
    }
    return l;
}
void put(int a){
    static int q[20]={};
    if(a<0) *wa++ = '-' , a = -a;
    for(;a;a/=10)q[++q[0]]=a%10;
    if(!q[0]) *wa++ = '0';
    for(;q[0];) *wa++ = (q[q[0]--] + '0');
}

int main(){
    read(n),read(m);
    for(int i=1,u,v;i<n;i++){
        read(u),read(v);
        Node(u,v),Node(v,u);
    }
    dfs(1,0);
    for(int j=1;j<lim;j++)
        for(int i=1;i<=tot-(1<<j)+1;i++)
            st[j][i] = (dep[st[j-1][i]] < dep[st[j-1][i+(1<<j-1)]] ? st[j-1][i] : st[j-1][i+(1<<j-1)]);
    for(int i=2;i<=tot;i++) lg[i] = lg[i>>1] + 1;
    for(int i=1;i<=m;i++){
        read(dat[i][0]),read(dat[i][1]);
        if(dat[i][0] == 0) read(dat[i][2]),read(dat[i][3]),sb[++cnt] = mp(dat[i][3],i);
        if(dat[i][0] == 1) dat[i][3] = dat[dat[i][1]][3];
    }
    sort(sb+1,sb+1+cnt);
    for(M=1;M<cnt;M<<=1);
    for(int i=1;i<=m;i++){
        if(dat[i][0] <= 1) 
            dat[i][3] = lower_bound(sb+1,sb+1+cnt,mp(dat[i][3],dat[i][0] == 0 ? i : dat[i][1])) - sb;
        if(dat[i][0] == 0) Insert(dat[i][3],dat[i][1],dat[i][2]);
        if(dat[i][0] == 1) Insert(dat[i][3],0,0);
        if(dat[i][0] == 2){
            if(chk(dat[i][1],pt[1])) put(-1);
            else put(sb[solve(1,1,M,dat[i][1])].first);
            *wa++ = '\n';
        }
    }
    fwrite(wb,1,wa-wb,stdout);
}

最后发一张该题的全解法：