A.kotori

做法很多，这里是 \(O((n+q)\log n)\) 线段树做法。实际上有 \(O(n)\) 做法。

当一个点被启动，你从这个点开始遍历，当遍历到一个点 \(x\)，它在此次遍历时的父亲是 \(fa\)，那么就相当于是——对于以 \(x\) 为根，除了以 \(fa\) 为根的子树，其他点都可以在去往装置时经过 \(x\)。

所以先随便选一个根，跑一遍 dfs 求出每个点的 dfs 序 \(dfn_x\) 和在这个树上的父亲 \(fath_x\)。在每次修改遍历到 \(x\) 时，如果它此次没有父亲（此次启动的就是它），就对全局修改；如果 \(fa=fath_x\)，则修改 \([dfn_x,dfn_x+siz_x-1]\)；如果 \(fa\not =fath_x\)，就对 \([1,dfn_{fa}-1]\) 与 \([dfn_{fa}+siz_{fa},n]\) 修改。相当于区间取 \(\min\)，单点求值，线段树即可。

考虑剪枝，发现一个边的一个方向只会经过一次，因为再跑一次所做的修改是一样的，所以可以在边上打标记，每个边经过一遍，所以修改变成均摊 \(O(n)\) 级别的。

发现会被菊花图卡，因为标记不是打在点上，所以每次可能会 \(O(n)\) 找需要走哪些边。发现一个点如果从两个不同方向遍历过来的话这个点的所有方向就都更新过了，因为第一次只会留下一个方向，第二次的 \(fa\) 与第一次不同所以第一次留下的方向也会更新。这样就不会被菊花图卡了。

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e6+10,INF=1e9+7;
int n,q,dfn[MAXN],tot,siz[MAXN],fath[MAXN];
int to[MAXN<<1],nxt[MAXN<<1],head[MAXN],cnt,vis[MAXN];
bool b[MAXN<<1];int t[MAXN<<2],ans;
inline void add(int x,int y)
{
    to[++cnt]=y,nxt[cnt]=head[x];
    head[x]=cnt;return ;
}
void dfs(int x,int fa=0)
{
    dfn[x]=++tot,siz[x]=1,fath[x]=fa;
    for(int i=head[x];i;i=nxt[i])
    {
        int y=to[i];if(y==fa) continue;
        dfs(y,x);siz[x]+=siz[y];
    }
    return ;
}
inline void spread(int p)
{
    t[p<<1]=min(t[p<<1],t[p]);
    t[p<<1|1]=min(t[p<<1|1],t[p]);
    return ;
}
void change(int l,int r,int p,int x,int y,int z)
{
    if(x<=l&&y>=r){t[p]=min(t[p],z);return ;}
    int mid=(l+r)>>1;spread(p);
    if(x<=mid) change(l,mid,p<<1,x,y,z);
    if(y>mid) change(mid+1,r,p<<1|1,x,y,z);
    return ;
}
int query(int l,int r,int p,int x)
{
    if(l==r) return t[p];
    int mid=(l+r)>>1;spread(p);
    return (x<=mid)?query(l,mid,p<<1,x):query(mid+1,r,p<<1|1,x);
}
void upd(int x,int fa=0)
{
    if(vis[x]==-1) return ;
    if(!fa) vis[x]=-1;
    else if(!vis[x]) vis[x]=fa;
    else if(vis[x]!=fa) vis[x]=-1;
    else return ;
    if(!fa) change(1,n,1,1,n,x);
    else if(fa==fath[x])
        change(1,n,1,dfn[x],dfn[x]+siz[x]-1,x);
    else
    {
        change(1,n,1,1,dfn[fa]-1,x);
        if(dfn[fa]+siz[fa]<=n)
            change(1,n,1,dfn[fa]+siz[fa],n,x);
    }
    for(int i=head[x];i;i=nxt[i])
        if(!b[i]&&to[i]!=fa) upd(to[i],x),b[i]=true;
    return ;
}
int main()
{
    freopen("kotori.in","r",stdin);
    freopen("kotori.out","w",stdout);
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>n>>q;
    for(int i=1,x,y;i<n;++i)
        cin>>x>>y,add(x,y),add(y,x);
    dfs(1);for(int i=1;i<=(n<<2);++i) t[i]=INF;
    while(q--)
    {
        int opt,x;cin>>opt>>x;
        x=(x+ans)%n+1;
        if(opt==1) upd(x);
        else cout<<(ans=query(1,n,1,dfn[x]))<<'\n';
    }
    return 0;
}

B.charlotte

这里是用 set 实现的换根 DP，时间复杂度 \(O(n\log n)\)。

记 \(siz_x,g_x,f_x\) 分别为 \(x\) 及其子树中有多少个关键点，所有关键点到 \(x\) 的距离和，将关键点尽可能合并后到 \(x\) 的距离和（我愿意理解为是将 \(g_x\) 缩到最小的值）。

当你钦定最后合并到 \(root\)，那么是否有解等价于 \([f_{root}=0]\)。

考虑朴素 DP，枚举所有根。有转移：

\(siz_x=[a_x=1]+\sum\limits_{y\in son(x)} siz_y\)
\(g_x=\sum\limits_{y\in son(x)} (g_y+siz_y)\)
\(f_x=\begin{cases} f_y+siz_y-(g_x-(g_y+siz_y)) & \exists y\in son(x),f_y+siz_y > g_x-(g_y+siz_y) \\ g_x\bmod 2 & \forall y\in son(x),f_y+siz_y\leq g_x-(g_y+siz_y) \end{cases}\)

\(\exists y\in son(x),f_y+siz_y > g_x-(g_y+siz_y)\)，实际含义是如果有一个 \(y\)，它及其子树到 \(x\) 所需的最少步数比 \(x\) 其他子树所提供的最多步数还多就不能被减完，最优就是尽可能的多处理这个子树；不然就考虑每次选出所有剩余 \(f_y\) 中最大的两个，一起 \(-1\)，这样就相当于最后只会剩 \([0,1]\) 个 \(1\)，就等于 \(g_x\) 的奇偶性。

考虑接下来换根 DP，先考虑 \(f_y+siz_y > g_x-(g_y+siz_y)\) 最多只会有 \(1\) 个，所以可以移项判断 \(f_y+siz_y+g_y+siz_y\) 与 \(g_x\) 的大小关系。\(f_x\) 的第一种转移也可以变成 \(f_y+siz_y+g_y+siz_y-g_x\)。

所以 \(siz_x,g_x\) 正常换根，再对于每个点开一个 set，将所有的 \(f_y+siz_y+g_y+siz_y\) 放到 \(x\) 对应的 set 中，这样就可以换根了。

其实我们每次只用到了最大值，所以如果不用 set 也可以直接维护，就可以不用 \(O(n)\) 了，但我感觉很麻烦。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
const int MAXN=1e6+10;
const long long INF=1e16+10;
int n,siz[MAXN];char a[MAXN];
long long f[MAXN],g[MAXN],ans=INF;
vector <int> v[MAXN];set <long long> s[MAXN];
inline void clear()
{
    for(int i=1;i<=n;++i) v[i].clear(),s[i].clear();
    ans=INF;return ;
}
void get_f(int x)
{
    if(s[x].empty()){f[x]=0;return ;}
    if(*s[x].rbegin()<=g[x]) f[x]=(g[x]&1?1:0);
    else f[x]=*s[x].rbegin()-g[x];return ;
}
void dfs(int x,int fa=0)
{
    siz[x]=(a[x]=='1');g[x]=0;
    for(int y:v[x])
    {
        if(y==fa) continue;dfs(y,x);
        siz[x]+=siz[y],g[x]+=g[y]+siz[y];
        s[x].insert(f[y]+siz[y]+g[y]+siz[y]);
    }
    get_f(x);return ;
}
void dp(int x,int fa=0)
{
    if(!f[x]) ans=min(ans,g[x]/2);
    for(int y:v[x])
    {
        if(y==fa) continue;
        siz[x]-=siz[y],g[x]-=g[y]+siz[y];
        s[x].erase(s[x].find(f[y]+siz[y]+g[y]+siz[y])),get_f(x);
        siz[y]+=siz[x],g[y]+=g[x]+siz[x];
        s[y].insert(f[x]+siz[x]+g[x]+siz[x]),get_f(y);
        dp(y,x);
        siz[y]-=siz[x],g[y]-=g[x]+siz[x];
        s[y].erase(s[y].find(f[x]+siz[x]+g[x]+siz[x])),get_f(y);
        siz[x]+=siz[y],g[x]+=g[y]+siz[y];
        s[x].insert(f[y]+siz[y]+g[y]+siz[y]),get_f(x);
    }
    return ;
}
int main()
{
    freopen("charlotte.in","r",stdin);
    freopen("charlotte.out","w",stdout);
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
    while(cin>>n)
    {
        for(int i=1;i<=n;++i) cin>>a[i];
        for(int i=1,x,y;i<n;++i)
            cin>>x>>y,v[x].push_back(y),v[y].push_back(x);
        dfs(1),dp(1);
        cout<<(ans==INF?-1:ans)<<'\n';clear();
    }
    return 0;
}

C.sagiri

先咕。

D.chtholly

考虑不在给出链上的点都相当于挂在这条链上的树。

有两种情况：一种情况是进入一颗树，在其中完成调头，然后原路返回；还有一种情况是进入一颗树，然后出去的时候走向进来的反方向，然后再倒着回去。

第一种情况需要可以从一个方向进入，树中有一个点有两个不同的长度大于等于链长的子树（计算长度时算上这个点）；第二种情况需要从两个方向都可以进入，树的最深深度大于等于链长（计算长度时算上树根）。

所以对于每颗树中你可以跑 dfs 得到信息。总和是 \(O(n)\) 的。

然后在链上，你能从右边/左边进入一棵树，一定是左端点可以大于等于这个树根的位置/右端点可以小于等于这个树根的位置。你考虑每次就相当于是当前链左边走进一棵树，再右边走进一棵树，再左边走进一棵树，再右边走进一棵树……不断拓展可以到的位置。

这个东西可以维护头尾两个指针，代表左链头可以到的最右端点，右链头可以到的最左端点，每棵树从每个方向进入一次，来更新一下这两个指针，时间复杂度 \(O(n)\) 的。

所有操作都是 \(O(n)\) 所以就是 \(O(n)\)。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXN=1e6+10;
int T,n,s,t,a[MAXN],len,d[MAXN],cur;
bool b[MAXN],f1[MAXN],f2[MAXN];
vector <int> v[MAXN];
inline void clear()
{
    for(int i=1;i<=n;++i)
        b[i]=f1[i]=f2[i]=d[i]=0,v[i].clear();
    len=0;return ;
}
bool get_line(int x,int cnt=1,int fa=0)
{
    if(x==t){a[len=cnt]=x;return true;}
    bool flag=false;
    for(int y:v[x]) if(y!=fa) flag|=get_line(y,cnt+1,x);
    if(flag) a[cnt]=x;return flag;
}
void dfs(int x,int fa=0)
{
    int se=0;d[x]=1;
    for(int y:v[x])
    {
        if(y==fa||b[y]) continue;
        dfs(y,x);
        if(d[y]+1>d[x]) se=d[x],d[x]=d[y]+1;
        else if(d[y]+1>se) se=d[y]+1;
    }
    f1[cur]|=(se>=len);return ;
}
inline void work()
{
    cin>>n>>s>>t;
    for(int i=1,x,y;i<n;++i)
        cin>>x>>y,v[x].push_back(y),v[y].push_back(x);
    get_line(s);for(int i=1;i<=len;++i) b[a[i]]=true;
    for(int x=1;x<=len;++x) cur=x,dfs(a[x],0),f2[x]=(d[a[x]]>=len);
    int l=1,r=len,prel=0,prer=len+1;
    while(l!=prel||r!=prer)
    {
        for(int i=prel+1;i<=l;++i) r=min(r,max(i+1,i+(len-d[a[i]])));prel=l;
        for(int i=prer-1;i>=r;--i) l=max(l,min(i-1,i-(len-d[a[i]])));prer=r;
    }
    for(int x=1;x<=len;++x)
    {
        if((l>=x||r<=x)&&f1[x]){cout<<"YES\n";return ;}
        if((l>=x&&r<=x)&&f2[x]){cout<<"YES\n";return ;}
    }
    cout<<"NO\n";return ;
}
int main()
{
    freopen("chtholly.in","r",stdin);
    freopen("chtholly.out","w",stdout);
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>T;
    while(T--) work(),clear();
    return 0;
}

526互联

NOIP 模拟14（NOIP A层联测27）

A.kotori

B.charlotte

C.sagiri

D.chtholly