【hiho1715】树的联通问题

题目大意:给定一棵 1~n 标号的树。Tree[L,R]表示最少需要选择的边的数量使得 L~R 号点两两连通。求:
\[ \sum_{L=1}^{n} \sum_{R=L}^{n} \operatorname{Tree}[L, R] \]

题解:
要求的是经过边的数量,可以考虑每条边对答案的贡献。
对于边 (u,v) ,定义一个特征序列 a[1...n],若 i 在以 u 为根的子树中,则 a[i]=1,否则 a[i]=0。发现若要求该边的贡献为 1,则选择的范围 a[l]-a[r] 中必须要既有 0 又有 1,这样才能跨过这条边,到达子树外面的节点。问题转化成了求对于树上每个节点的特征序列来说,既有 0 又有 1 的区间的个数和是多少。但是这个问题并不好求,可以转化为求特征序列中,只有 0 或 1 的区间个数,再用总共的区间个数减掉这些即可。因此,可以采用线段树来维护区间最长前后缀 0/1 的长度,区间合并的时候只需处理左区间的后缀和右区间的前缀即可完成。树上的问题还需要进行线段树合并来完成,时间复杂度为 \(O(nlogn)\)

代码如下

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn=1e5+10;
typedef long long LL;

int n; LL ans;
vector<int> G[maxn];
struct node{
    #define ls(o) t[o].lc
    #define rs(o) t[o].rc
    int lc,rc,lmx0,lmx1,rmx0,rmx1;
    LL sum0,sum1;
}t[maxn*20];
int tot,rt[maxn];
inline void pushup(int o,int l,int r){
    int mid=l+r>>1;
    if(!ls(o))t[ls(o)].sum0=(LL)(mid-l+1)*(mid-l+2)/2,t[ls(o)].lmx0=t[ls(o)].rmx0=mid-l+1;
    if(!rs(o))t[rs(o)].sum0=(LL)(r-mid)*(r-mid+1)/2,t[rs(o)].lmx0=t[rs(o)].rmx0=r-mid;
    t[o].sum0=t[ls(o)].sum0+t[rs(o)].sum0+(LL)t[ls(o)].rmx0*t[rs(o)].lmx0;
    t[o].sum1=t[ls(o)].sum1+t[rs(o)].sum1+(LL)t[ls(o)].rmx1*t[rs(o)].lmx1;
    t[o].lmx0=t[ls(o)].lmx0==mid-l+1?t[ls(o)].lmx0+t[rs(o)].lmx0:t[ls(o)].lmx0;
    t[o].lmx1=t[ls(o)].lmx1==mid-l+1?t[ls(o)].lmx1+t[rs(o)].lmx1:t[ls(o)].lmx1;
    t[o].rmx0=t[rs(o)].rmx0==r-mid?t[rs(o)].rmx0+t[ls(o)].rmx0:t[rs(o)].rmx0;
    t[o].rmx1=t[rs(o)].rmx1==r-mid?t[rs(o)].rmx1+t[ls(o)].rmx1:t[rs(o)].rmx1;
}
void insert(int &o,int l,int r,int pos){
    if(!o)o=++tot;
    if(l==r){t[o].lmx1=t[o].rmx1=t[o].sum1=1;return;}
    int mid=l+r>>1;
    if(pos<=mid)insert(ls(o),l,mid,pos);
    else insert(rs(o),mid+1,r,pos);
    pushup(o,l,r);
}
int merge(int x,int y,int l,int r){
    if(!x||!y)return x+y;
    if(l==r)return t[x].sum1?x:y;
    int mid=l+r>>1;
    ls(x)=merge(ls(x),ls(y),l,mid);
    rs(x)=merge(rs(x),rs(y),mid+1,r);
    return pushup(x,l,r),x;
}
void dfs(int u,int fa){
    for(auto v:G[u]){
        if(v==fa)continue;
        dfs(v,u);
        rt[u]=merge(rt[u],rt[v],1,n);
    }
    insert(rt[u],1,n,u);
    LL ret=(LL)n*(n+1)/2-t[rt[u]].sum0-t[rt[u]].sum1;
    if(u!=1)ans+=ret;
}

void read_and_parse(){
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        G[x].pb(y),G[y].pb(x);
    }
}
void solve(){
    dfs(1,0);
    printf("%lld\n",ans);
}
int main(){
    read_and_parse();
    solve();
    return 0;
} 

【hiho1715】树的联通问题

上一篇:基于Dapper的开源Lambda超轻量扩展,Dapper.Common


下一篇:Android Studio 引用AAR包