我是奶龙我才是奶龙

Undead2008 · 2025-05-09 21:59:03 · 题解

COTS 2025 题解合集

先考虑吸完尘回到 1 怎么做，你一定会使用开着的吸尘器将每条边经过两遍，现在就变成了最小化关着吸尘器走的路。

下文中的讨论不认为点 1 是叶子，无论他度数是几。

考虑对每个 i=1\sim n 分别求解，i=1 时你需要拿着关着的吸尘器经过每个不是叶子的节点，i=2 时你不用经过这些节点形成的连通块中的叶子节点，i=3 时你不用经过 i=2 时经过的节点形成的连通块中的叶子节点，以此类推，可以发现这是一个删叶子的过程，直接模拟就行。

然后就是不回到 1 的情况，这时你一定会在 1 能到达的最远点停留，将所有答案减去 1 到最远点的距离即可。

#include"bits/stdc++.h"
#ifdef REANI
    #include"windows.h"
    using namespace std;
    void SetMemoryLimit(SIZE_T MB){
        HANDLE job=CreateJobObject(NULL,NULL);
        assert(job!=NULL);
        JOBOBJECT_EXTENDED_LIMIT_INFORMATION info={0};
        info.BasicLimitInformation.LimitFlags=JOB_OBJECT_LIMIT_PROCESS_MEMORY;
        info.ProcessMemoryLimit=MB;
        assert(SetInformationJobObject(job,JobObjectExtendedLimitInformation,&info,sizeof(info))&&AssignProcessToJobObject(job,GetCurrentProcess()));
    }
#else
    using namespace std;
#endif
const int maxn = 3e5+10;
int n,q,Dg[maxn],A[maxn],Dp[maxn];
vector<int>e[maxn];
int M;
void D(int p,int Fa){
    M=max(M,Dp[p]);
    for(auto To:e[p]){
        if(To==Fa)continue;
        Dp[To]=Dp[p]+1;
        D(To,p);
    }
}
int main(){
    #ifdef REANI
        SetMemoryLimit(512*1048576);
    #endif
    ios::sync_with_stdio(0),cin.tie(nullptr);
    cin>>n>>q;
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
        Dg[u]++,Dg[v]++;
    }
    D(1,0);
    vector<int>Db;
    for(int i=1;i<=n;i++)
        if(Dg[i]==1&&i!=1)
            Db.push_back(i);
    int S=n;
    for(int i=1;i<=n;i++){
        vector<int>Nw;
        for(auto x:Db){
            for(auto To:e[x]){
                if(Dg[To]==-1)continue;
                Dg[To]--;
                if(Dg[To]==1&&To!=1)Nw.push_back(To);
            }
            Dg[x]=-1,S--;
        }
        Db=Nw;
        A[i]=2*(n-1)+2*(S-1)-M;
    }
    for(int i=1,T;i<=q;i++)
        cin>>T,cout<<A[T]<<' ';
    cout<<'\n';
}