CF258E 【Little Elephant and Tree】

· · 题解

题目

看到没啥人写水发题解

一开始的想法：

假如每次操作都是一个节点，那么只需要在根节点打上标记，然后一遍dfs下来就好了。这提醒我们，把信息记录在根上，然后一路传递下来

对于节点a，设和它关联的节点为\{b_1,b_2,...,b_k\}

很显然的，b_i的深度越小，子树的大小就越大

那直接取b_i中深度最小的吗？不一定，因为b_i,b_j的子树可能没有交集

然后就想，只要把有交集的b保留深度最大的，然后剩下的b_i的子树大小的和就是a的答案（还要加上从他祖先传递下来的）

那怎么判断有没有交集呢？交集肯定是放在区间上啊，还是看子树，那直接求个dfs序不就转变为区间上的问题了吗

准备开始码的时候，想到：判断一个点b是否和前面的有交集，就直接在维护dfs序的线段树上单点查询，如果有查到，再判断深度大小，如果当前这个深度更浅就要把上一个去掉，好麻烦QWQ

如果没有交集，线段树上当然可以直接加；如果有交集的话，为什么不能直接加呢？既然都有一颗线段树了，为什么还要去维护没有交集的\{b\}呢？每次区间修改，区间询问有多少个不为0的数不就好了吗

因为计算完p以及其子树答案后，回溯到父亲时，p及其子树的信息肯定是要去掉的

所以线段树要支持的操作：区间+1/-1以及询问整个区间有多少个不为0的数

注意到+1,-1操作一定是成对存在的，所以可以直接写成标记永久化

细节：

1、如果当前节点p有关联的节点，除了修改关联节点子树内的，还有p子树内的

2、每个节点在dfs序上是有两个的，所以最后答案是不为0的数除以2再减1（不包括自己）

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N=1e6+10;
int tot,cnt;
int fir[N],dfn[N][2],ans[N];
vector<int>opt[N];
struct edge
{
    int to;
    int nxt;
}e[2*N];
inline void add(int x,int y)
{
    e[++tot].to=y; e[tot].nxt=fir[x]; fir[x]=tot;
    e[++tot].to=x; e[tot].nxt=fir[y]; fir[y]=tot;
}
struct tree
{
    int left,right;
    int val,cnt;
}t[8*N];
inline void build(int p,int l,int r)
{
    t[p].left=l,t[p].right=r;
    if(l==r) return;
    int mid=(t[p].left+t[p].right)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
}
inline void pushup(int p)
{
    if(t[p].val>0) t[p].cnt=t[p].right-t[p].left+1;
    else t[p].cnt=t[p*2].cnt+t[p*2+1].cnt;
}
inline void change(int p,int l,int r,int c)
{
    if(l<=t[p].left&&r>=t[p].right)
    {
        t[p].val+=c;
        pushup(p);
        return;
    }
    int mid=(t[p].left+t[p].right)/2;
    if(l<=mid) change(p*2,l,r,c);
    if(r>mid) change(p*2+1,l,r,c);
    pushup(p);
}
inline void dfs1(int p,int fa)
{
    dfn[p][0]=++cnt;
    for(int i=fir[p];i;i=e[i].nxt)
        if(e[i].to!=fa) dfs1(e[i].to,p);
    dfn[p][1]=++cnt;
}
inline void dfs2(int p,int fa)
{
    if(opt[p].size()) change(1,dfn[p][0],dfn[p][1],1);
    for(int i=0;i<opt[p].size();i++)
        change(1,dfn[opt[p][i]][0],dfn[opt[p][i]][1],1);
    if(t[1].cnt) ans[p]=t[1].cnt/2-1;
    for(int i=fir[p];i;i=e[i].nxt)
        if(e[i].to!=fa) dfs2(e[i].to,p);
    if(opt[p].size()) change(1,dfn[p][0],dfn[p][1],-1);
    for(int i=0;i<opt[p].size();i++)
        change(1,dfn[opt[p][i]][0],dfn[opt[p][i]][1],-1);
}
int main()
{
    int n,m,a,b;
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    dfs1(1,0);
    build(1,1,2*n);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        opt[a].push_back(b);
        opt[b].push_back(a);    
    }
    dfs2(1,0);
    for(int i=1;i<=n;i++)
        printf("%d ",ans[i]);
    return 0;
}