NEERC2017 Laminar Family 树链剖分+LCA

题目链接

http://codeforces.com/gym/101630/attachments/download/6401/20172018-acmicpc-northeastern-european-regional-contest-neerc-17-en.pdf

题意

给出一棵树和一组操作，操作的格式是给出$u、v$两个节点，并将该节点所确定的路径上的节点全部加入到一个新的集合里面去。
如果所有的集合中任意两个均满足，要么互相包含，要么不相交，则输出Yes，否则输出No。

题解

互相包含这个条件不太好用，因为它相当于是两个条件，因此我们对这个条件做一下操作：我们求出所有出现过的路径长度(求长度可以使用LCA来求)，并将这些操作按照长度从大到小排序，这样的话集合的包含就只是一个方向的了，即已经出现过的集合包含当前的集合。这样对我们解决这道题有很大帮助。

我们在从长到短遍历路径的时候，先查看这条路径上的颜色是否多于一种，如果出现多种颜色，就说明当前的集合会与之前的集合有交叉，那么就输出No，否则的话，就把沿路的点全都染上一种新的颜色。

如果所有的路径都遍历完成，没有出现矛盾，那么输出Yes。

小问题：如何判定一条链上只有一种颜色呢？
我们可以用数字给颜色编号，然后检查这条链上的最大值和这条链上的最小值是否相等。

思路似乎很简单，这里有几个实现的细节：
1. 树链剖分对树上的点进行操作。
2. 线段树要求支持区间set值的操作，和区间询问最大最小值的操作。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <assert.h>
using namespace std;
#define pr(x) cout<<#x<<":"<<x<<endl
const int maxn = 2e5+7;
const int inf = 1e9;
int head[maxn];
int sz[maxn],fa[maxn],son[maxn],dep[maxn],top[maxn],w[maxn];
int pa[maxn][22];
int idx,cnt,n,m;
struct edge{
    int v,nxt;
}Es[maxn<<1];
struct segtree{
    int mxval[maxn<<2];
    int mival[maxn<<2];
    int tag[maxn<<2];
    void pushup(int rt){
        mxval[rt] = max(mxval[rt*2],mxval[rt*2+1]);
        mival[rt] = min(mival[rt*2],mival[rt*2+1]);
    }
    void pushdown(int rt){
        if(tag[rt]){
            mxval[rt*2] = mival[rt*2] = tag[rt];
            mxval[rt*2+1] = mival[rt*2+1] = tag[rt];
            tag[rt*2] = tag[rt*2+1] = tag[rt];
            tag[rt] = 0;
        }
    }
    void update(int rt,int l,int r,int ul,int ur,int val){
        if(l > ur || r < ul) return ;
        if(ul <= l && r <= ur){
            mxval[rt] = mival[rt] = val;
            tag[rt] = val;
            return ;
        }
        int mid = (l + r) / 2;
        pushdown(rt);
        update(rt*2,l,mid,ul,ur,val);
        update(rt*2+1,mid+1,r,ul,ur,val);
        pushup(rt);
    }
    pair<int,int> query(int rt,int l,int r,int ul,int ur){
        if(l > ur || r < ul) return {inf,-inf};
        if(ul <= l && r <= ur) return {mival[rt],mxval[rt]};
        pushdown(rt);
        int mid = (l+r)/2;
        pair<int,int> a = query(rt*2,l,mid,ul,ur);
        pair<int,int> b = query(rt*2+1,mid+1,r,ul,ur);
        return {min(a.first,b.first),max(a.second,b.second)};
    }
}seg;
void init(){
    idx = cnt = 0;
    memset(head,-1,sizeof(head));
}
void addedge(int i,int j){
    Es[cnt].v = j,Es[cnt].nxt = head[i],head[i] = cnt++;
}
void dfs1(int u,int f,int dp){
    son[u] = 0;fa[u] = f;dep[u] = dp;sz[u] = 1;
    for(int e = head[u];e != -1;e = Es[e].nxt){
        int v = Es[e].v;
        if(v == fa[u]) continue;
        dfs1(v,u,dp+1);
        sz[u] += sz[v];
        if(sz[v] > sz[son[u]])
            son[u] = v;
    }
}

void dfs2(int u,int tp){
    top[u] = tp;
    w[u] = ++idx;
    if(son[u]) 
        dfs2(son[u],tp);
    else 
        return ;
    for(int e = head[u];e != -1;e = Es[e].nxt){
        int v = Es[e].v;
        if(v == son[u] || v == fa[u]) continue;
        dfs2(v,v);
    }
}

bool getp(int u,int v){
    pair<int,int> pans = {inf,-inf};
    int fu = top[u],fv = top[v];
    while(fu != fv){
        if(dep[fu] < dep[fv])
            swap(fu,fv),swap(u,v);
        auto p = seg.query(1,1,n,w[fu],w[u]);
        u = fa[fu];
        fu = top[u];
        pans.first = min(pans.first,p.first);
        pans.second = max(pans.second,p.second);
    }
    if(u == v) {
        auto p = seg.query(1,1,n,w[u],w[u]);
        return min(p.first,pans.first) == max(p.second,pans.second);
    }
    if(dep[u] < dep[v]) swap(u,v);
    auto p = seg.query(1,1,n,w[v],w[u]);
    return min(pans.first,p.first) == max(pans.second,p.second);
}
void modify(int u,int v,int x){
    int fu = top[u],fv = top[v];
    while(fu != fv){
        if(dep[fu] < dep[fv])
            swap(fu,fv),swap(u,v);
        seg.update(1,1,n,w[fu],w[u],x);
        u = fa[fu];
        fu = top[u];
    }
    if(u == v) {
        seg.update(1,1,n,w[u],w[u],x);
        return ;
    }
    if(dep[u] < dep[v]) swap(u,v);
    seg.update(1,1,n,w[v],w[u],x);
}
int lca(int u,int v){
    if(dep[u] < dep[v]) swap(u,v);
    int d = dep[u] - dep[v];
    for(int i = 0;i <= 20;++i) 
        if(d & (1<<i)) u = pa[u][i];
    for(int i = 20;i >= 0;--i){
        if(pa[u][i] == pa[v][i]) continue;
        u = pa[u][i],v = pa[v][i];
    }
    if(u != v) u = pa[u][0],v = pa[v][0];
    assert(u == v); 
    return u;
}
int uu[maxn],vv[maxn],dd[maxn],ss[maxn];
int main(){
    init();
    cin>>n>>m;
    for(int i = 0;i < n-1;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        addedge(u,v);
        addedge(v,u);
    }
    dfs1(1,1,0);
    dfs2(1,1);
    for(int i = 1;i <= n;++i) pa[i][0] = fa[i];
    for(int t = 1;t <= 20;++t) for(int i = 1;i <= n;++i){
        pa[i][t] = pa[pa[i][t-1]][t-1];
    }
    for(int i = 0;i < m;++i){
        int u,v,d;
        scanf("%d%d",&u,&v);
        d = dep[u] + dep[v] - 2*dep[lca(u,v)]+1;
        uu[i] = u,vv[i] = v,dd[i] = d,ss[i] = i;
    } 
    sort(ss,ss+m,[](int a,int b){return dd[a] > dd[b];});
    for(int i = 0;i < m;++i){
        int id = ss[i];
        //pr(uu[id]);pr(vv[id]);
        if(!getp(uu[id],vv[id])){
            return 0*puts("No");
        }
        modify(uu[id],vv[id],i+1);
    }
    puts("Yes");
    return 0;
}