20联赛集训day5 题解

Author： RainAir
发布时间：October 18, 2020
689views
No comments
361 words
Categories：题解

A

枚举每个矩形，前缀和优化即可。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 2000+5;

char str[MAXN];
int n,k;
int sm[MAXN][MAXN];

int main(){
    scanf("%d%d",&n,&k);
    FOR(i,1,n){
        scanf("%s",str+1);
        FOR(j,1,n){
            sm[i][j] = sm[i][j-1]+sm[i-1][j]-sm[i-1][j-1]+str[j]-'0';
        }
    }
    int ans = 0;
    FOR(i,k,n){
        FOR(j,k,n){
            ans = std::max(ans,sm[i][j]-sm[i-k][j]-sm[i][j-k]+sm[i-k][j-k]);
        }
    }
    printf("%d\n",ans);
    return 0;
}

B

$O(n2^n)$ 可以做任意图，只需要考虑如何判断一个图是强连通图：有一个点在正图和反图上都能到达所有点。

这个题要注意到竞赛图缩点后 DAG 上拓扑序小的点向拓扑序大的点都有连边。

所以我们如果得到了一个集合 $S$ 是强连通的，设属于它的所有的点的出边的交为 $T$，对于任意 $R \subset T,R \neq \emptyset$，一定 $S | R$ 是不合法的区间。而我们发现这样顶多会不重不漏遍历每个状态一次，所以均摊复杂度是 $O(2^n)$ 的。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 24+1;
int n;
int e[MAXN],out[(1<<MAXN)+3],pc[(1<<MAXN)+3];
#define lowbit(x) ((x)&(-(x)))
bool f[(1<<MAXN)+3];

inline void Solve(){
    scanf("%d",&n);CLR(e,0);CLR(f,0);
    FOR(i,0,n-1){
        FOR(j,0,n-1){
            int x;scanf("%d",&x);
            e[i] |= (x<<j);
        }
    }
    out[0] = (1<<n)-1;
    FOR(S,1,(1<<n)-1) out[S] = out[S-lowbit(S)]&e[pc[lowbit(S)]];
    int ans = 1;
    FOR(S,1,(1<<n)-1){
        if(!f[S]){
            ans++;
            for(int T = out[S];T;T = (T-1)&out[S]){
                f[S|T] = 1;
            }
        }
    }
    printf("%d\n",ans);
}

int main(){
    FOR(i,0,23) pc[1<<i] = i;
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}

C

我们先来观察一下什么情况是不合法的。我们按轮考虑：

设数字 $i$ 在三个人的序列出现的位置分别是 $pa_i,pb_i,pc_i$；设在第 $i$ 轮三个人选的数字是 $x,y,z$，合法当且仅当

$x,y,z$ 互不相同
$x$ 在 $B,C$ 的喜好序列出现的位置在 $y,z$ 后面，其余同理

所以我们发现我们如果确定了这三个人选什么数的话， C 的排列的方案数都是不变的，可以设 $g_{i,j}$ 表示考虑确定了 C 的前 $i$ 位，已经进行了 $j$ 轮的方案数，转移可以枚举这一位是否是 C 最终选的数字中的一个位置，如果是就 $g_{i,j} = g_{i-1,j-1}(2j-(i-j))$，否则就直接 $g_{i,j} = g_{i-1,j}$。

然后我们现在就是要对有多少种不同的选数方案进行dp；设 $f_{i,j,k}$ 表示 A 选了它自己的序列中第 $i$ 个，B 选了第 $j$ 个，C 还空着 $k$ 个的方案数。枚举下一次选的位置 $i',j'$，我们发现首先 $i'$ 在 B 中出现的位置不能在 $j'$ 之前，$j'$ 在 A 中出现的位置不能在 $i'$ 之前。如果在 $[i,i'],[j,j']$ 有个数字没有被选过，一定是被 $C$ 选了，我们设这样的数字数量为 $x$。转移就是 $f_{i,j,k} \to k^{\underline x}f_{i',j',k+1-x}$。

这样复杂度就是 $O(n^6)$ 的。

首先我们可以预处理找 $x$ 的过程，复杂度变成了 $O(n^5)$。

我们考虑每次可以不用一起枚举 $i',j'$ ，可以设 $f1,f2$ 表示两个人的 dp 数组，所以复杂度变成了 $O(n^4)$。

我们发现每次只需要考虑 $i+1$ 的位置是否选择，选择了就换到另一个人的 dp 数组转移，复杂度 $O(n^3)$。注意到我们从第一个人转移到第二个人不用考虑任何限制，在第二个人转移回去的时候统一考虑即可。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 400+5;
const int ha = 1e9 + 7;
int n,a[MAXN],b[MAXN],pa[MAXN],pb[MAXN]; 
int f1[MAXN][MAXN][MAXN],f2[MAXN][MAXN][MAXN];
// A选了第i个,B选了第j个,C还能用k个 
int g[MAXN][MAXN];
// 前i个 选了j个 

inline void add(int &x,int y){
    x += y;if(x >= ha) x -= ha;
}

int main(){
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",a+i),pa[a[i]] = i;
    FOR(i,1,n) scanf("%d",b+i),pb[b[i]] = i;
    f1[1][1][1] = 1;
    FOR(i,1,n+1){
        FOR(j,1,n+1){
            FOR(k,0,n/3){
                if(f1[i][j][k]){
                    if(k && pb[a[i+1]] > j) add(f1[i+1][j][k-1],1ll*f1[i][j][k]*k%ha);
                    if(pb[a[i+1]] <= j) add(f1[i+1][j][k],f1[i][j][k]);
                    add(f2[i+1][j][k],f1[i][j][k]);
                }
                if(f2[i][j][k]){
                    if(k && pa[b[j+1]] > i) add(f2[i][j+1][k-1],1ll*f2[i][j][k]*k%ha);
                    if(pa[b[j+1]] <= i) add(f2[i][j+1][k],f2[i][j][k]);
                    if(i == n+1 || j == n+1 || (pb[a[i]] > j+1 && pa[b[j+1]] > i)) add(f1[i][j+1][k+1],f2[i][j][k]);
                }
            }
        }
    }
    g[0][0] = 1;
    FOR(i,0,n-1){
        FOR(j,0,n/3){
            add(g[i+1][j+1],g[i][j]);
            if(3*j-i > 0) add(g[i+1][j],1ll*g[i][j]*(3*j-i)%ha);
        }
    }
    int ans = 1ll*f1[n+1][n+1][1]*g[n][n/3]%ha; 
    printf("%d\n",ans);
    return 0;
}

D

树上路径问题如果不会了可以考虑链分治，分开维护重链和轻边。

对于重链的颜色直接用线段树维护区间赋值即可。

轻边的颜色有两种可能改变：

有一次修改经过了这个轻边
有一次修改经过了轻边的两个端点之一，并没有经过轻边

我们只需要知道这两个操作最后一次的时间，就能判断出轻边的颜色，线段树维护即可。

要注意是轻边的两个端点都要查，因为可能有某个修改的 lca 到父亲的边是轻边的情况。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 3e5 + 5;

int n,q;

struct Edge{
    int to,nxt;
}e[MAXN<<1];
int head[MAXN],cnt;

inline void add(int u,int v){
    e[++cnt] = (Edge){v,head[u]};head[u] = cnt;
    e[++cnt] = (Edge){u,head[v]};head[v] = cnt;
}

#define lc ((x)<<1)
#define rc ((x)<<1|1)

int sm[MAXN<<2],ts[MAXN<<2],cov[MAXN<<2],tag[MAXN<<2];
// 0表示染黑 数字表示有个时间

inline void cover1(int x,int l,int r,int d){
    sm[x] = (r-l+1)*d;cov[x] = d;
}

inline void cover2(int x,int l,int r,int d){
    ts[x] = tag[x] = d;
}

inline void pushdown(int x,int l,int r){
    int mid = (l + r) >> 1;
    if(cov[x] != -1){
        cover1(lc,l,mid,cov[x]);
        cover1(rc,mid+1,r,cov[x]);
        cov[x] = -1;
    }
    if(tag[x] != -1){
        cover2(lc,l,mid,tag[x]);
        cover2(rc,mid+1,r,tag[x]);
        tag[x] = -1;
    }
}

inline void modify(int x,int l,int r,int L,int R,int d){
    if(L > R) return;
    if(l == L && r == R){
        cover1(x,l,r,d?0:1);
        if(d) cover2(x,l,r,d);
        return;
    }
    int mid = (l + r) >> 1;pushdown(x,l,r);
    if(R <= mid) modify(lc,l,mid,L,R,d);
    else if(L > mid) modify(rc,mid+1,r,L,R,d);
    else modify(lc,l,mid,L,mid,d),modify(rc,mid+1,r,mid+1,R,d);
    sm[x] = sm[lc]+sm[rc];
}

inline void modify2(int x,int l,int r,int L,int R,int d){
    if(L > R) return;
    if(l == L && r == R){
        cover2(x,l,r,d);
        return;
    }
    int mid = (l + r) >> 1;pushdown(x,l,r);
    if(R <= mid) modify2(lc,l,mid,L,R,d);
    else if(L > mid) modify2(rc,mid+1,r,L,R,d);
    else modify2(lc,l,mid,L,mid,d),modify2(rc,mid+1,r,mid+1,R,d);
    sm[x] = sm[lc]+sm[rc];
}

inline int query(int x,int l,int r,int L,int R){
    if(L > R) return 0;
    if(l == L && r == R) return sm[x];
    int mid = (l + r) >> 1;pushdown(x,l,r);
    if(R <= mid) return query(lc,l,mid,L,R);
    if(L > mid) return query(rc,mid+1,r,L,R);
    return query(lc,l,mid,L,mid)+query(rc,mid+1,r,mid+1,R);
}

inline int queryt(int x,int l,int r,int p){
    if(l == r) return ts[x];
    int mid = (l + r) >> 1;pushdown(x,l,r);
    if(p <= mid) return queryt(lc,l,mid,p);
    else return queryt(rc,mid+1,r,p);
}

inline void build(int x,int l,int r){
    sm[x] = r-l+1;tag[x] = cov[x] = -1;
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(lc,l,mid);build(rc,mid+1,r);
}

int dfn[MAXN],tp[MAXN],son[MAXN],dep[MAXN],fa[MAXN],sz[MAXN],_;

inline void dfs1(int v){
    dep[v] = dep[fa[v]]+1;sz[v] = 1;
    for(int i = head[v];i;i = e[i].nxt){
        if(e[i].to == fa[v]) continue;
        fa[e[i].to] = v;dfs1(e[i].to);
        sz[v] += sz[e[i].to];
        son[v] = sz[son[v]] > sz[e[i].to] ? son[v] : e[i].to;
    }
}

inline void dfs2(int v,int tp=1){
    dfn[v] = ++_;::tp[v] = tp;
    if(son[v]) dfs2(son[v],tp);
    for(int i = head[v];i;i = e[i].nxt){
        if(e[i].to == fa[v] || e[i].to == son[v]) continue;
        dfs2(e[i].to,e[i].to);
    }
}

int tim[MAXN];

inline void modify(int x,int y){
    if(son[x]) modify(1,1,n,dfn[son[x]],dfn[son[x]],0);
    if(son[y]) modify(1,1,n,dfn[son[y]],dfn[son[y]],0);
    while(tp[x] != tp[y]){
        if(dep[tp[x]] < dep[tp[y]]) std::swap(x,y);
        if(son[tp[x]]) modify(1,1,n,dfn[son[tp[x]]],dfn[x],_);
        modify2(1,1,n,dfn[tp[x]],dfn[tp[x]],_);
        tim[tp[x]] = _;
        x = fa[tp[x]];
        if(son[x]) modify(1,1,n,dfn[son[x]],dfn[son[x]],0);
    }
    if(dep[x] > dep[y]) std::swap(x,y);
    modify(1,1,n,dfn[x],dfn[y],_);
    modify(1,1,n,dfn[x],dfn[x],0);
}

inline int query(int x,int y){
    int res = 0;
    while(tp[x] != tp[y]){
        if(dep[tp[x]] < dep[tp[y]]) std::swap(x,y);
        if(son[tp[x]]) res += query(1,1,n,dfn[son[tp[x]]],dfn[x]);
        if(tim[tp[x]] < std::max(queryt(1,1,n,dfn[fa[tp[x]]]),queryt(1,1,n,dfn[tp[x]]))) res++;
        x = fa[tp[x]];
    }
    if(dep[x] > dep[y]) std::swap(x,y);
    if(son[x]) res += query(1,1,n,dfn[son[x]],dfn[y]);
    return res;
}

int main(){
    scanf("%d",&n);
    FOR(i,2,n){
        int u,v;scanf("%d%d",&u,&v);
        add(u,v);
    }
    scanf("%d",&q);
    dfs1(1);dfs2(1);build(1,1,n);
    FOR(i,1,n) tim[i] = -1;
    FOR(i,1,q){
        _ = i;int opt,x,y;scanf("%d%d%d",&opt,&x,&y);
        // if(i == 2) FF = 1;
        if(opt == 1) modify(x,y);
        else printf("%d\n",query(x,y));
    }
    return 0;
}

Last modification：July 6th, 2021 at 07:01 pm

如果觉得我的文章对你有用，请随意赞赏

20联赛集训day5 题解

RainAir • 2020 年 10 月 18 日

A

枚举每个矩形，前缀和优化即可。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 2000+5;

char str[MAXN];
int n,k;
int sm[MAXN][MAXN];

int main(){
    scanf("%d%d",&n,&k);
    FOR(i,1,n){
        scanf("%s",str+1);
        FOR(j,1,n){
            sm[i][j] = sm[i][j-1]+sm[i-1][j]-sm[i-1][j-1]+str[j]-'0';
        }
    }
    int ans = 0;
    FOR(i,k,n){
        FOR(j,k,n){
            ans = std::max(ans,sm[i][j]-sm[i-k][j]-sm[i][j-k]+sm[i-k][j-k]);
        }
    }
    printf("%d\n",ans);
    return 0;
}

B

$O(n2^n)$ 可以做任意图，只需要考虑如何判断一个图是强连通图：有一个点在正图和反图上都能到达所有点。

这个题要注意到竞赛图缩点后 DAG 上拓扑序小的点向拓扑序大的点都有连边。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 24+1;
int n;
int e[MAXN],out[(1<<MAXN)+3],pc[(1<<MAXN)+3];
#define lowbit(x) ((x)&(-(x)))
bool f[(1<<MAXN)+3];

inline void Solve(){
    scanf("%d",&n);CLR(e,0);CLR(f,0);
    FOR(i,0,n-1){
        FOR(j,0,n-1){
            int x;scanf("%d",&x);
            e[i] |= (x<<j);
        }
    }
    out[0] = (1<<n)-1;
    FOR(S,1,(1<<n)-1) out[S] = out[S-lowbit(S)]&e[pc[lowbit(S)]];
    int ans = 1;
    FOR(S,1,(1<<n)-1){
        if(!f[S]){
            ans++;
            for(int T = out[S];T;T = (T-1)&out[S]){
                f[S|T] = 1;
            }
        }
    }
    printf("%d\n",ans);
}

int main(){
    FOR(i,0,23) pc[1<<i] = i;
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}

C

我们先来观察一下什么情况是不合法的。我们按轮考虑：

设数字 $i$ 在三个人的序列出现的位置分别是 $pa_i,pb_i,pc_i$；设在第 $i$ 轮三个人选的数字是 $x,y,z$，合法当且仅当

$x,y,z$ 互不相同
$x$ 在 $B,C$ 的喜好序列出现的位置在 $y,z$ 后面，其余同理

这样复杂度就是 $O(n^6)$ 的。

首先我们可以预处理找 $x$ 的过程，复杂度变成了 $O(n^5)$。

我们考虑每次可以不用一起枚举 $i',j'$ ，可以设 $f1,f2$ 表示两个人的 dp 数组，所以复杂度变成了 $O(n^4)$。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 400+5;
const int ha = 1e9 + 7;
int n,a[MAXN],b[MAXN],pa[MAXN],pb[MAXN]; 
int f1[MAXN][MAXN][MAXN],f2[MAXN][MAXN][MAXN];
// A选了第i个,B选了第j个,C还能用k个 
int g[MAXN][MAXN];
// 前i个 选了j个 

inline void add(int &x,int y){
    x += y;if(x >= ha) x -= ha;
}

int main(){
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",a+i),pa[a[i]] = i;
    FOR(i,1,n) scanf("%d",b+i),pb[b[i]] = i;
    f1[1][1][1] = 1;
    FOR(i,1,n+1){
        FOR(j,1,n+1){
            FOR(k,0,n/3){
                if(f1[i][j][k]){
                    if(k && pb[a[i+1]] > j) add(f1[i+1][j][k-1],1ll*f1[i][j][k]*k%ha);
                    if(pb[a[i+1]] <= j) add(f1[i+1][j][k],f1[i][j][k]);
                    add(f2[i+1][j][k],f1[i][j][k]);
                }
                if(f2[i][j][k]){
                    if(k && pa[b[j+1]] > i) add(f2[i][j+1][k-1],1ll*f2[i][j][k]*k%ha);
                    if(pa[b[j+1]] <= i) add(f2[i][j+1][k],f2[i][j][k]);
                    if(i == n+1 || j == n+1 || (pb[a[i]] > j+1 && pa[b[j+1]] > i)) add(f1[i][j+1][k+1],f2[i][j][k]);
                }
            }
        }
    }
    g[0][0] = 1;
    FOR(i,0,n-1){
        FOR(j,0,n/3){
            add(g[i+1][j+1],g[i][j]);
            if(3*j-i > 0) add(g[i+1][j],1ll*g[i][j]*(3*j-i)%ha);
        }
    }
    int ans = 1ll*f1[n+1][n+1][1]*g[n][n/3]%ha; 
    printf("%d\n",ans);
    return 0;
}

D

树上路径问题如果不会了可以考虑链分治，分开维护重链和轻边。

对于重链的颜色直接用线段树维护区间赋值即可。

轻边的颜色有两种可能改变：

有一次修改经过了这个轻边
有一次修改经过了轻边的两个端点之一，并没有经过轻边

我们只需要知道这两个操作最后一次的时间，就能判断出轻边的颜色，线段树维护即可。

要注意是轻边的两个端点都要查，因为可能有某个修改的 lca 到父亲的边是轻边的情况。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 3e5 + 5;

int n,q;

struct Edge{
    int to,nxt;
}e[MAXN<<1];
int head[MAXN],cnt;

inline void add(int u,int v){
    e[++cnt] = (Edge){v,head[u]};head[u] = cnt;
    e[++cnt] = (Edge){u,head[v]};head[v] = cnt;
}

#define lc ((x)<<1)
#define rc ((x)<<1|1)

int sm[MAXN<<2],ts[MAXN<<2],cov[MAXN<<2],tag[MAXN<<2];
// 0表示染黑 数字表示有个时间

inline void cover1(int x,int l,int r,int d){
    sm[x] = (r-l+1)*d;cov[x] = d;
}

inline void cover2(int x,int l,int r,int d){
    ts[x] = tag[x] = d;
}

inline void pushdown(int x,int l,int r){
    int mid = (l + r) >> 1;
    if(cov[x] != -1){
        cover1(lc,l,mid,cov[x]);
        cover1(rc,mid+1,r,cov[x]);
        cov[x] = -1;
    }
    if(tag[x] != -1){
        cover2(lc,l,mid,tag[x]);
        cover2(rc,mid+1,r,tag[x]);
        tag[x] = -1;
    }
}

inline void modify(int x,int l,int r,int L,int R,int d){
    if(L > R) return;
    if(l == L && r == R){
        cover1(x,l,r,d?0:1);
        if(d) cover2(x,l,r,d);
        return;
    }
    int mid = (l + r) >> 1;pushdown(x,l,r);
    if(R <= mid) modify(lc,l,mid,L,R,d);
    else if(L > mid) modify(rc,mid+1,r,L,R,d);
    else modify(lc,l,mid,L,mid,d),modify(rc,mid+1,r,mid+1,R,d);
    sm[x] = sm[lc]+sm[rc];
}

inline void modify2(int x,int l,int r,int L,int R,int d){
    if(L > R) return;
    if(l == L && r == R){
        cover2(x,l,r,d);
        return;
    }
    int mid = (l + r) >> 1;pushdown(x,l,r);
    if(R <= mid) modify2(lc,l,mid,L,R,d);
    else if(L > mid) modify2(rc,mid+1,r,L,R,d);
    else modify2(lc,l,mid,L,mid,d),modify2(rc,mid+1,r,mid+1,R,d);
    sm[x] = sm[lc]+sm[rc];
}

inline int query(int x,int l,int r,int L,int R){
    if(L > R) return 0;
    if(l == L && r == R) return sm[x];
    int mid = (l + r) >> 1;pushdown(x,l,r);
    if(R <= mid) return query(lc,l,mid,L,R);
    if(L > mid) return query(rc,mid+1,r,L,R);
    return query(lc,l,mid,L,mid)+query(rc,mid+1,r,mid+1,R);
}

inline int queryt(int x,int l,int r,int p){
    if(l == r) return ts[x];
    int mid = (l + r) >> 1;pushdown(x,l,r);
    if(p <= mid) return queryt(lc,l,mid,p);
    else return queryt(rc,mid+1,r,p);
}

inline void build(int x,int l,int r){
    sm[x] = r-l+1;tag[x] = cov[x] = -1;
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(lc,l,mid);build(rc,mid+1,r);
}

int dfn[MAXN],tp[MAXN],son[MAXN],dep[MAXN],fa[MAXN],sz[MAXN],_;

inline void dfs1(int v){
    dep[v] = dep[fa[v]]+1;sz[v] = 1;
    for(int i = head[v];i;i = e[i].nxt){
        if(e[i].to == fa[v]) continue;
        fa[e[i].to] = v;dfs1(e[i].to);
        sz[v] += sz[e[i].to];
        son[v] = sz[son[v]] > sz[e[i].to] ? son[v] : e[i].to;
    }
}

inline void dfs2(int v,int tp=1){
    dfn[v] = ++_;::tp[v] = tp;
    if(son[v]) dfs2(son[v],tp);
    for(int i = head[v];i;i = e[i].nxt){
        if(e[i].to == fa[v] || e[i].to == son[v]) continue;
        dfs2(e[i].to,e[i].to);
    }
}

int tim[MAXN];

inline void modify(int x,int y){
    if(son[x]) modify(1,1,n,dfn[son[x]],dfn[son[x]],0);
    if(son[y]) modify(1,1,n,dfn[son[y]],dfn[son[y]],0);
    while(tp[x] != tp[y]){
        if(dep[tp[x]] < dep[tp[y]]) std::swap(x,y);
        if(son[tp[x]]) modify(1,1,n,dfn[son[tp[x]]],dfn[x],_);
        modify2(1,1,n,dfn[tp[x]],dfn[tp[x]],_);
        tim[tp[x]] = _;
        x = fa[tp[x]];
        if(son[x]) modify(1,1,n,dfn[son[x]],dfn[son[x]],0);
    }
    if(dep[x] > dep[y]) std::swap(x,y);
    modify(1,1,n,dfn[x],dfn[y],_);
    modify(1,1,n,dfn[x],dfn[x],0);
}

inline int query(int x,int y){
    int res = 0;
    while(tp[x] != tp[y]){
        if(dep[tp[x]] < dep[tp[y]]) std::swap(x,y);
        if(son[tp[x]]) res += query(1,1,n,dfn[son[tp[x]]],dfn[x]);
        if(tim[tp[x]] < std::max(queryt(1,1,n,dfn[fa[tp[x]]]),queryt(1,1,n,dfn[tp[x]]))) res++;
        x = fa[tp[x]];
    }
    if(dep[x] > dep[y]) std::swap(x,y);
    if(son[x]) res += query(1,1,n,dfn[son[x]],dfn[y]);
    return res;
}

int main(){
    scanf("%d",&n);
    FOR(i,2,n){
        int u,v;scanf("%d%d",&u,&v);
        add(u,v);
    }
    scanf("%d",&q);
    dfs1(1);dfs2(1);build(1,1,n);
    FOR(i,1,n) tim[i] = -1;
    FOR(i,1,q){
        _ = i;int opt,x,y;scanf("%d%d%d",&opt,&x,&y);
        // if(i == 2) FF = 1;
        if(opt == 1) modify(x,y);
        else printf("%d\n",query(x,y));
    }
    return 0;
}

20联赛集训day5 题解

A

B

C

D

Leave a Comment Cancel reply

NOI2021 退役记

SDOI2020 退役记

I'm back

点双连通分量 & 圆方树学习笔记

CSP2019 游记

网络流建模总结

ZR 2020普转提七连测day4

「CF1097G」Vladislav and a Great Legend

小c的岛屿题解

「优化」内存池

20联赛集训day5 题解

A

B

C

D