[Luogu5327][ZJOI2019]语言(树上差分+线段树合并)

首先可以想到对每个点统计出所有经过它的链的并所包含的点数，然后可以直接得到答案。根据实现不同有下面几种方法。
三个log：假如对每个点都存下经过它的链并S[x]，那么每新加一条路径进来的时候，相当于在路径上所有点的S中都加入这条路径。树剖之后，相当于对log个区间中的点都加入log个区间。具体实现有树剖后线段树维护虚树、矩形扫描线、线段树+set存区间等多种方法，这里不再多说。
两个log：先树剖，然后对每个点开一棵线段树存储它的S，由于题中没有修改，所以可以树上差分+线段树合并，这样可以将方法一中“需要修改的区间数”的log去掉了。
一个log：发现就是对每个点求所有经过它的路径的端点的斯坦纳树（这里一个点集的斯坦纳树是指原树上最小的点集，满足包含这个点集且连通）。考虑如何暴力求一个点集的斯坦纳树，那显然就是将它们按DFS序排序后，所有点深度之和减去每对相邻点LCA的深度和。为了方便我们将点集中强制加入根，最后求出结果后再减去所有点LCA的深度的两倍。以DFS序为下标建线段树，每个点维护它所代表的DFS区间中，所有在点集中的点（加上根）构成的斯坦纳树的大小。两个区间的合并就是两边的斯坦纳树大小之和，减去左边区间里在点集中的DFS序最大的点与右边区间里在点集中的DFS序最小的点的LCA的深度，于是再维护区间里在点集中的DFS序最大/小的点分别是谁即可。同样使用树上差分+线段树合并，就可以将方法一中“每个修改区间中要加入的区间数”的log去掉了。

（参考https://www.luogu.org/blog/Sooke/solution-p5327）

 #include<cstdio>

 #include<vector>

 #include<algorithm>

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 #define For(i,x) for (int i=h[x],k; i; i=nxt[i])

 typedef long long ll;

 using namespace std;

 const int N=,M=,K=;

 int n,m,x,y,tim,cnt,nd,d[N],lg[N],rt[N],fa[N],dfn[N],st[N][];

 int v[M],ls[M],rs[M],s[M],t[M],c[M],h[N],to[N],nxt[N];

 ll ans;

 vector<int>del[N];

 void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; }

 void dfs(int x){

     d[x]=d[fa[x]]+; st[++tim][]=x; dfn[x]=tim;

     For(i,x) if ((k=to[i])!=fa[x]) fa[k]=x,dfs(k),st[++tim][]=x;

 }

 void init(){

     rep(j,,lg[tim]) rep(i,,tim-(<<j)+){

         int x=st[i][j-],y=st[i+(<<(j-))][j-];

         st[i][j]=d[x]<d[y] ? x : y;

     }

 }

 int lca(int x,int y){

     if (!x || !y) return ;

     x=dfn[x]; y=dfn[y];

     if (x>y) swap(x,y);

     int t=lg[y-x+]; x=st[x][t]; y=st[y-(<<t)+][t];

     return d[x]<d[y] ? x : y;

 }

 void upd(int x){

     v[x]=v[ls[x]]+v[rs[x]]-d[lca(t[ls[x]],s[rs[x]])];

     s[x]=s[ls[x]] ? s[ls[x]] : s[rs[x]];

     t[x]=t[rs[x]] ? t[rs[x]] : t[ls[x]];

 }

 void mdf(int &x,int L,int R,int p,int k){

     if (!x) x=++nd;

     if (L==R){ c[x]+=k; v[x]=(c[x]?d[p]:); s[x]=t[x]=(c[x]?p:); return; }

     int mid=(L+R)>>;

     if (dfn[p]<=mid) mdf(ls[x],L,mid,p,k); else mdf(rs[x],mid+,R,p,k);

     upd(x);

 }

 int merge(int x,int y,int L,int R){

     if (!x || !y) return x|y;

     if (L==R){ c[x]+=c[y]; v[x]|=v[y]; s[x]|=s[y]; t[x]|=t[y]; return x; }

     int mid=(L+R)>>; ls[x]=merge(ls[x],ls[y],L,mid); rs[x]=merge(rs[x],rs[y],mid+,R);

     upd(x); return x;

 }

 void solve(int x){

     For(i,x) if ((k=to[i])!=fa[x]) solve(k);

     int ed=del[x].size()-;

     rep(i,,ed) mdf(rt[x],,tim,del[x][i],-);

     ans+=v[rt[x]]-d[lca(s[rt[x]],t[rt[x]])]; rt[fa[x]]=merge(rt[fa[x]],rt[x],,tim);

 }

 int main(){

     freopen("a.in","r",stdin);

     freopen("a.out","w",stdout);

     scanf("%d%d",&n,&m);

     rep(i,,n<<) lg[i]=lg[i>>]+;

     rep(i,,n) scanf("%d%d",&x,&y),add(x,y),add(y,x);

     dfs(); init();

     rep(i,,m){

         scanf("%d%d",&x,&y); int l=lca(x,y);

         mdf(rt[x],,tim,x,); mdf(rt[x],,tim,y,);

         mdf(rt[y],,tim,x,); mdf(rt[y],,tim,y,);

         del[l].push_back(x); del[l].push_back(y);

         del[fa[l]].push_back(x); del[fa[l]].push_back(y);

     }

     solve(); printf("%lld\n",ans/);

     return ;

 }

巴特西

[Luogu5327][ZJOI2019]语言(树上差分+线段树合并)

最新文章

热门文章