#29 TLE 求助
查看原帖
#29 TLE 求助
371818
juruo999楼主2022/10/24 22:40

调了很久,CF 上 #29 一直 TLE,应该不是常数的问题。记录

// LUOGU_RID: 91405805
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

typedef long long ll;
#define il inline
const ll inf=1145141919810;

inline int Read()
{
	int x = 0,f = 1;
	char a = getchar();
	while(!isdigit(a)) {if(a == '-') f = -1;a = getchar();}
	while(isdigit(a)) {x = (x << 1) + (x << 3) + (a ^ '0');a = getchar();}
	return x * f;
}

int n;
vector<int> E[300005];
int fa[300005],dfn[300005],dep[300005],siz[300005],hc[300005],tp[300005];
int cnt=0;

void dfs(int u){
    dep[u]=dep[fa[u]]+1;siz[u]=1;hc[u]=-1;dfn[u]=++cnt;
    for(auto v:E[u]){
        siz[u]+=siz[v];
        if(v==fa[u]) continue;
        fa[v]=u;dfs(v);
        if(hc[u]==-1 || siz[hc[u]]<siz[v]) hc[u]=v;
    }
}
void dfs2(int u,int t){
    tp[u]=t;
    if(hc[u]!=-1) dfs2(hc[u],t);
    for(auto v:E[u]){
        if(v==fa[u] || v==hc[u]) continue;
        dfs2(v,v);
    }
}
int lca(int u,int v){
    while(tp[u]!=tp[v]){
        if(dep[tp[u]]<dep[tp[v]]) swap(u,v);
        u=fa[tp[u]];
    }
    if(dep[u]<dep[v]) swap(u,v);
    return v;
}

int m;
int p[300005];
bool vis[300005];

int t[300005],tot;
vector<int> S[300005];
int f[300005],g[300005];

bool cmp(int u,int v){ return dfn[u]<dfn[v]; }
bool cmpeq(int u,int v){ return dfn[u]==dfn[v]; }

void work(){
    m=Read();
    for(int i=1;i<=m;i++) p[i]=Read(),t[i]=p[i],vis[p[i]]=1;
    tot=m;
    sort(p+1,p+m+1,cmp);
    for(int i=1;i<=m;i++) if(vis[fa[p[i]]]){
        cout<<"-1\n";
        for(int i=1;i<=m;i++) vis[p[i]]=0;
        return;
    }
    for(int i=1;i<m;i++){
        t[++tot]=lca(p[i],p[i+1]);
    }
    sort(t+1,t+tot+1,cmp);
    tot=unique(t+1,t+tot+1,cmpeq)-t-1;
    for(int i=2;i<=tot;i++){
        S[lca(t[i-1],t[i])].push_back(t[i]);
    }
    for(int i=tot;i>=1;i--){
        int u=t[i];int c=0;
        // cout<<"KEY "<<u<<"\n";
        g[u]=vis[u];f[u]=0;
        for(auto v:S[u]){
            // cout<<"  SON"<<v<<"\n";
            // if(vis[u] && vis[v]){ brk=1;break; }
            f[u]+=f[v];
            c+=g[v];
        }
        if(vis[u]){
            f[u]+=c;
        }else{
            if(c>1) f[u]++;
            else if(c==1) g[u]=1;
            else g[u]=0;
        }
        // cout<<"-- RES "<<f[u]<<"\n";
    }
    printf("%d\n",f[t[1]]);
    for(int i=1;i<=tot;i++) S[t[i]].clear();
    for(int i=1;i<=m;i++) vis[p[i]]=0;
}

int main(){

    // ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    n=Read();
    for(int i=1;i<n;i++){
        int u=Read(),v=Read();
        E[u].push_back(v);
        E[v].push_back(u);
    }

    dfs(1);dfs2(1,1);

    int q=Read();
    while(q--){
        work();
    }

    return 0;
}
2022/10/24 22:40
加载中...