求助虚树 DP WA #11
查看原帖
求助虚树 DP WA #11
239192
淸梣ling楼主2023/5/20 15:56

WA 在了 #11 的第 6 个,求各位 dalao 帮忙找一下 bug。qwq

#include<bits/stdc++.h>
using namespace std;

#define bmax(x,y) (dep[x]<dep[y] ? x : y)

vector<int> v[100100],vv[100100];
int dep[100100],id[100100],dfn[200100],cnt;
int st[200100][20];
bool isc[100100];
int ans=0;

bool cmp(const int x, const int y) { return id[x]<id[y]; }
void init(int x, int fa)
{
    dfn[++cnt]=x; id[x]=cnt; dep[x]=dep[fa]+1;
    for(int y : v[x])
    if(y!=fa)
    {
        init(y, x);
        dfn[++cnt]=x;
    }
}
void initST()
{
    for(int i=1; i<=cnt; i++) st[i][0]=dfn[i];
    for(int j=1; j<20; j++)
    for(int i=1; i+(1<<j)-1<=cnt; i++)
    st[i][j]=bmax(st[i][j-1], st[i+(1<<j-1)][j-1]);
}
int LCA(int x, int y)
{
    int l=id[x],r=id[y];
    if(l>r) swap(l, r);
    int t=log2(r-l+1);
    return bmax(st[l][t], st[r-(1<<t)+1][t]);
}
void build(vector<int> b)
{
    static int stk[100100],top;
    sort(b.begin(), b.end(), cmp);
    
    stk[top=1]=1;
    for(int x : b)
    if(x!=1)
    {
        int lca=LCA(x, stk[top]);
        if(lca!=stk[top])
        {
            while(dfn[lca]<dfn[stk[top-1]])
            {
                vv[stk[top-1]].push_back(stk[top]);
                --top;
            }
            vv[lca].push_back(stk[top]);
            if(lca!=stk[top-1]) stk[top]=lca;
            else --top;
        }
        stk[++top]=x;
    }
    for(int i=1; i<top; i++)
    vv[stk[i]].push_back(stk[i+1]);
}
int dfs(int x)
{
    int cnt=0;
    for(int y : vv[x])
    {
        if(isc[y]&&isc[x]&&dep[y]-dep[x]==1) ans=-1e9;
        cnt+=dfs(y);
    }
    vv[x].clear();
    
    if(isc[x])
    {
        ans+=cnt;
        return 1;
    }
    else if(cnt>1)
    {
        ++ans;
        return 0;
    }
    else
    return cnt;
}
void work()
{
    vector<int> b;
    int n;

    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        int x;
        scanf("%d", &x);
        b.push_back(x); isc[x]=1;
    }

    ans=0;
    build(b); dfs(1);
    printf("%d\n", ans<0 ? -1 : ans);
    for(int x : b) isc[x]=0;
}
int main()
{
    int n,q;

    cin>>n;
    for(int i=1; i<n; i++)
    {
        int x,y;
        scanf("%d%d", &x, &y);
        v[x].push_back(y);
        v[y].push_back(x);
    }

    cin>>q; init(1, 0); initST();
    for(int i=1; i<=q; i++) work();
    return 0;
}
2023/5/20 15:56
加载中...