JZOJ 6813 送信

两个方向：从信到旅行或从旅行到信。

最后都是三维偏序。
树套树过不去。

没什么好说的，写这题解主要是留个 CDQ 板子（

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
    for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
    w && (x = -x);
}

const int N = 1e5;
const int LG = 18;
int n,m,q;
int to[(N << 1) + 5],pre[(N << 1) + 5],first[N + 5];
inline void add(int u,int v)
{
    static int tot = 0;
    to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
int fa[N + 5],dep[N + 5],id[N + 5],rk[N + 5],sz[N + 5];
int son[N + 5],top[N + 5];
int cur[N + 5];
void dfs(int p)
{
    int tot = 0,flag;
    for(;;)
    {
        flag = 0;
        if(!id[p])
            rk[id[p] = ++tot] = p,sz[p] = 1,cur[p] = first[p];
        for(register int i = cur[p];i;i = pre[i])
        {
            cur[p] = pre[i];
            if(to[i] ^ fa[p])
            {
                fa[to[i]] = p,dep[to[i]] = dep[p] + 1,p = to[i],flag = 1;
                break;
            }
        }
        if(!flag)
            if(fa[p])
            {
                sz[fa[p]] += sz[p];
                if(!son[fa[p]] || sz[p] > sz[son[fa[p]]])
                    son[fa[p]] = p;
                p = fa[p];
            }
            else
                break;
    }
}
inline int get(int p,int u)
{
    while(top[p] ^ top[u])
    {
        if(fa[top[p]] == u)
            return top[p];
        p = fa[top[p]];
    }
    return son[u];
}
int ans[N + 5],qry_tot,tot;
struct s_operation
{
    int op,x,y,w;
} opt[N * 16 + 5],buf[N * 16 + 5];
namespace BIT
{
    #define lowbit(x) ((x) & -(x))
    int c[N + 5];
    inline void update(int x,int k)
    {
        for(;x <= n;x += lowbit(x))
            c[x] += k; 
    }
    inline int query(int x)
    {
        int ret = 0;
        for(;x;x -= lowbit(x))
            ret += c[x];
        return ret;
    }
}
void update(int x,int y,int l,int r)
{
    opt[++tot] = (s_operation){0,x,l,1},
    opt[++tot] = (s_operation){0,x,r + 1,-1},
    opt[++tot] = (s_operation){0,y + 1,l,-1},
    opt[++tot] = (s_operation){0,y + 1,r + 1,1};
}
void update(int x,int y)
{
    id[x] > id[y] && (swap(x,y),1);
    int t = x;
    if(id[x] <= id[y] && id[y] < id[x] + sz[x])
        x = get(y,x),
        id[x] && (update(1,id[x] - 1,id[y],id[y] + sz[y] - 1),1),
        id[x] + sz[x] <= n && (update(id[x] + sz[x],n,id[y],id[y] + sz[y] - 1),1);
    else
        update(id[x],id[x] + sz[x] - 1,id[y],id[y] + sz[y] - 1);
}
void solve(int l,int r)
{
    if(l == r)
        return ;
    int mid = l + r >> 1;
    solve(l,mid),solve(mid + 1,r);
    int i = l,j = mid + 1,k = l;
    while(i <= mid && j <= r)
        if(opt[i].x <= opt[j].x)
        {
            if(!opt[i].op)
                BIT::update(opt[i].y,opt[i].w);
            buf[k++] = opt[i++];
        }
        else
        {
            if(opt[j].op)
                ans[-opt[j].w] += BIT::query(opt[j].y);
            buf[k++] = opt[j++];
        }
    while(i <= mid)
    {
        if(!opt[i].op)
            BIT::update(opt[i].y,opt[i].w);
        buf[k++] = opt[i++];
    }
    while(j <= r)
    {
        if(opt[j].op)
            ans[-opt[j].w] += BIT::query(opt[j].y);
        buf[k++] = opt[j++];
    }
    for(register int i = l;i <= mid;++i)
        if(!opt[i].op)
            BIT::update(opt[i].y,-opt[i].w);
    for(register int i = l;i <= r;++i)
        opt[i] = buf[i];
}
int main()
{
    freopen("letter.in","r",stdin),freopen("letter.out","w",stdout);
    read(n),read(m),read(q);
    int u,v;
    for(register int i = 2;i <= n;++i)
        read(u),read(v),add(u,v),add(v,u);
    dep[1] = 1,dfs(1);
    for(register int i = 1;i <= n;++i)
        top[rk[i]] = rk[i] == son[fa[rk[i]]] ? top[fa[rk[i]]] : rk[i];
    for(;m;--m)
        read(u),read(v),update(u,v);
    for(int op;q;--q)
        read(op),read(u),read(v),
        op == 1 ? (++qry_tot,opt[++tot] = (s_operation){1,id[u],id[v],-qry_tot},opt[++tot] = (s_operation){1,id[v],id[u],-qry_tot},1) : (update(u,v),1);
    solve(1,tot);
    for(register int i = 1;i <= qry_tot;++i)
        printf("%d\n",ans[i]);
}