2021牛客暑期多校训练营7 F.xay loves trees（线段树+滑窗）

题目链接：https://ac.nowcoder.com/acm/contest/11258/F

分析

在第二棵树上跑一边dfs，得到了dfs序，每个点就有一个区间$[l,r]$，如下图所示

不难发现如果取的两个点的区间是有交集的，那么他们就是在同一条链上的（就不符合要求）。
我们就可以维护一棵线段树，加入一个点就将其区间全部加1，如果总区间内的最大值大于1就说明现在的点集的区间是有交集的。所以线段树只需要维护区间最大值。
如果加入一个点之后还是符合要求的，那么滑块长度就增长1，否则滑块长度不变。
具体看代码

代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
const int N = 3e5 + 10;int n, sz, head, ans;
int l[N], r[N], idx;
int st[N];
vector<int> g1[N], g2[N];struct node{
    int maxn, lazy;
}tree[N<<2];void push_up(int rt)
{
    tree[rt].maxn = max(tree[rt << 1].maxn, tree[rt << 1 | 1].maxn);
}void push_down(int rt)
{
    if(tree[rt].lazy == 0) return ;tree[rt << 1].lazy += tree[rt].lazy;tree[rt << 1 | 1].lazy += tree[rt].lazy;tree[rt << 1].maxn += tree[rt].lazy;tree[rt << 1 | 1].maxn += tree[rt].lazy;tree[rt].lazy = 0;
}void build(int rt, int L,int R)
{
    if(L == R){
    tree[rt].maxn = tree[rt].lazy = 0;return ;}tree[rt].maxn = tree[rt].lazy = 0;int mid = (L + R) >> 1;build(rt << 1, L, mid);build(rt << 1 | 1, mid + 1, R);return ;
}void update(int rt, int L, int R, int x, int y, int val)
{
    if(L >= x && R <= y){
    tree[rt].maxn += val;tree[rt].lazy += val;return;}push_down(rt);int mid = (L + R) >> 1;if(x <= mid) update(rt << 1, L, mid, x, y, val);if(y > mid) update(rt << 1 | 1, mid + 1, R, x, y, val);push_up(rt);
}int query(int rt, int L, int R, int x, int y)
{
    if(L >= x && R <= y) return tree[rt].maxn;push_down(rt);int mid = (L + R) >> 1;int maxn = 0;if(x <= mid) maxn = max(maxn, query(rt << 1, L, mid, x, y));if(y > mid) maxn = max(maxn, query(rt << 1 | 1, mid + 1, R, x, y));return maxn;
}void dfn(int u, int fa)
{
    int v;l[u] = ++idx;for(int i=0;i<g2[u].size();i++){
    v = g2[u][i];if(v == fa) continue;dfn(v, u);}r[u] = idx;
}void dfs(int u, int fa, int step)
{
    int ifmov = 0;st[step] = u;update(1, 1, n, l[u], r[u], 1);if(query(1, 1, n, 1, n) > 1)//说明有交集滑块头向后缩{
    update(1, 1, n, l[st[head]], r[st[head]], -1);head++;ifmov = 1;}else sz++;ans = max(ans, sz);for(int i=0;i<g1[u].size();i++){
    int v = g1[u][i];if(v == fa) continue;dfs(v, u, step + 1);}if(ifmov)//开始回溯{
    head--;update(1, 1, n, l[st[head]], r[st[head]], 1);}else sz--;update(1, 1, n, l[u], r[u], -1);return;
}int main()
{
    int T = 1;scanf("%d",&T);while(T--){
    ans = 0;scanf("%d",&n);for(int i=1;i<=n;i++) g1[i].clear(), g2[i].clear();build(1, 1, n);for(int i=1;i<n;i++){
    int u,v;scanf("%d%d",&u,&v);g1[u].pb(v);g1[v].pb(u);}for(int i=1;i<n;i++){
    int u,v;scanf("%d%d",&u,&v);g2[u].pb(v);g2[v].pb(u);}idx = 0;dfn(1, 0);//处理出每个点的区间sz = 0;head = 1;dfs(1, 0, 1);printf("%d\n",ans);}return 0;
}