【树剖 线段树】 题解 P6572 【[BalticOI 2017] Railway】

· · 题解

思路

对于每一个副部长，我们把被他选择的点按dfs序从小到大排序，依次使相临两点最短路径上的边的权值+1。最后判断有哪些边的权值不小与2*k即可。

举个例子

如图：若副部长选择的点为4,5,7。(可以发现本来只算一次的边，恰好算了2次)

从4到5，从5到7，从7到4。

Code

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <iomanip>
using namespace std;
const int N=401000;
int n,m,k,num,tot=0,dotot=0,tp=0;
int lst[N],dfn[N],sum[N],laz[N],ls[N],rs[N],q[N],u[N],v[N];
int id[N],dep[N],top[N],son[N],siz[N],fa[N];
struct A
{
    int fir,nex,go,type;
}a[N];
inline bool cmp(int E,int F)
{
    return dfn[E]<dfn[F];
}
void add(int x,int y)
{
    a[++tot].nex=a[x].fir;
    a[x].fir=tot;
    a[tot].go=y;
}
inline int read()
{
    int x=0,minus=0;char ch;
    while (!isdigit(ch=getchar())) minus|=(ch=='-');
    while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return minus?-x:x;
}
void dfs1(int x,int f)
{
    dfn[x]=++dotot;//dfs序
    fa[x]=f;
    dep[x]=dep[f]+1;
    siz[x]=1;
    for (register int i=a[x].fir;i;i=a[i].nex)
    {
        int y=a[i].go;
        if (y==f) continue;
        dfs1(y,x);
        siz[x]+=siz[y];
        if (siz[son[x]]<siz[y]) son[x]=y;
    }
}
void dfs2(int x,int topf)
{
    id[x]=++dotot;//线段树用的
    top[x]=topf;
    if (!son[x]) return ;
    dfs2(son[x],topf);
    for (register int i=a[x].fir;i;i=a[i].nex)
    {
        int y=a[i].go;
        if (y==fa[x]||y==son[x]) continue;
        dfs2(y,y);
    }
}
void build(int k,int l,int r)
{
    ls[k]=l,rs[k]=r;
    if (l==r) return ;
    int mid=(l+r)>>1;
    build(k<<1,l,mid),build(k<<1|1,mid+1,r);
}
void down(int k)
{
    if (laz[k]==0) return ;
    laz[k<<1]+=laz[k];
    laz[k<<1|1]+=laz[k];
    sum[k<<1]+=(rs[k<<1]-ls[k<<1]+1)*laz[k];
    sum[k<<1|1]+=(rs[k<<1|1]-ls[k<<1|1]+1)*laz[k];
    laz[k]=0;
}
void change(int k,int x,int y)
{
    if (ls[k]>=x&&rs[k]<=y)
    {
        sum[k]+=rs[k]-ls[k]+1;
        laz[k]++;
        return ;
    }
    down(k);
    if (x<=rs[k<<1]) change(k<<1,x,y);
    if (y>=ls[k<<1|1]) change(k<<1|1,x,y);
    sum[k]=sum[k<<1]+sum[k<<1|1];
}
inline int cheak(int k,int x)
{
    if (ls[k]==rs[k]) return sum[k];
    down(k);
    if (x<=rs[k<<1]) return cheak(k<<1,x);
    else return cheak(k<<1|1,x);
}
void chain(int x,int y)
{
    while (top[x]!=top[y])
    {
        if (dep[top[x]]<dep[top[y]]) swap(x,y);
        change(1,id[top[x]],id[x]);
        x=fa[top[x]];
    }
    if (x==y) return ;
    if (dep[x]>dep[y]) swap(x,y);
    change(1,id[son[x]],id[y]);
}
signed main()
{
    n=read(),m=read(),k=read();
    for (register int i=1,x,y;i<n;++i)
    x=read(),y=read(),add(x,y),add(y,x),u[i]=x,v[i]=y;
    tot=0,dfs1(1,0),dotot=0,dfs2(1,1),build(1,1,n);//预处理
    while (m--)
    {
        num=read();
        for (register int i=1;i<=num;++i) lst[i]=read();
        sort(lst+1,lst+1+num,cmp);//按dfs序排序
        for (register int i=1;i<num;++i) chain(lst[i],lst[i+1]);
        chain(lst[1],lst[num]);//依次使相临两点最短路径上的边的权值+1
    }
    for (register int i=1;i<n;++i)
    {
        if (dep[u[i]]<dep[v[i]]) swap(u[i],v[i]);//树剖把边权存到儿子那了
        if (cheak(1,id[u[i]])>=2*k) q[++tp]=i;
    }
    printf("%d\n",tp);
    for (register int i=1;i<=tp;++i) printf("%d ",q[i]);//输出答案
    return 0;
}