首页 > 其他分享 >fsajakslfkaslf

fsajakslfkaslf

时间:2024-09-13 18:23:58浏览次数:9  
标签:dist g2 fsajakslfkaslf res int edge e2

点击查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = stdin,*OutFile = stdout;
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 1e6 + 10;
struct Edge{
    struct EDGE{int to,next,w;}edge[N<<1];
    int head[N],cnt;
    inline void add(int u,int v,int w){edge[++cnt] = {v,head[u],w};head[u] = cnt;}
}e1,e2;
int n,q,k,h[N];
int fa[N],dfn[N],dist[N],dep[N],siz[N],top[N],tot,son[N];
bitset<N> Q;
void dfs1(int x){
    siz[x] = 1;dep[x] = dep[fa[x]] + 1;dfn[x] = ++tot;
    for(int i = e1.head[x]; i;i = e1.edge[i].next){
        int y = e1.edge[i].to;
        if(y == fa[x]) continue;
        dist[y] = dist[x] + 1;
        fa[y] = x;dfs1(y);
        siz[x] += siz[y];
        if(siz[son[x]] < siz[y]) son[x] = y;
    }
}
void dfs2(int x,int t){
    top[x] = t;
    if(son[x]) dfs2(son[x],t);else return;
    for(int i = e1.head[x]; i;i = e1.edge[i].next){
        int y = e1.edge[i].to;
        if(y == fa[x] || y == son[x]) continue;
        dfs2(y,y);
    }
}
inline int LCA(int x,int y){
    int fx = top[x],fy = top[y];
    while(fx != fy){
        if(dep[fx] < dep[fy]) swap(fx,fy),swap(x,y);
        x = fa[fx];
        fx = top[x];
    }
    if(dep[x] > dep[y]) swap(x,y);
    return x;
}
inline bool cmp(int x,int y){return dfn[x] < dfn[y];}
vector<int> use;
inline void clear_vtree(){
    for(auto i:use) e2.head[i] = 0;
    e2.cnt = 0;vector<int> ().swap(use);
    rep(i,1,k,1) Q[h[i]] = false;
}
inline void build(){
    sort(h + 1,h + 1 + k,cmp);
    vector<int> res;
    res.emplace_back(1);
    rep(i,1,k - 1,1){
        res.emplace_back(h[i]);
        res.emplace_back(LCA(h[i + 1],h[i]));
    }
    res.emplace_back(h[k]);
    sort(res.begin(),res.end(),cmp);
    res.erase(unique(res.begin(),res.end()),res.end());
    int len = res.size();
    rep(i,0,len-2,1){
        int lca = LCA(res[i],res[i + 1]);
        e2.add(lca,res[i + 1],dist[res[i + 1]] - dist[lca]);
        use.emplace_back(lca);use.emplace_back(res[i + 1]);
    }
}
ll f[N],g1[N],g2[N],sz[N],ans1,ans2,ans3;
const ll inf = 9223372036854775806;
void dp(int x){
    sz[x] = Q[x];
    int res = 0;
    for(int i = e2.head[x]; i;i = e2.edge[i].next){
        int y = e2.edge[i].to;
        res++;
        dp(y);
        sz[x] += sz[y];
        f[x] += f[y] + sz[y]*(e2.edge[i].w);
        int res1 = g1[y]+e2.edge[i].w,res2 = g2[y]+e2.edge[i].w;
        if(res1 < g1[x]){
            g1[x] = res1;
            if(res2 < g2[x]) g2[x] = res2;
        }
        else{if(res1 < g2[x]) g2[x] = res1;}
    }
    ans1 += (res>1||Q[x])*f[x];
    // ans2 = min(ans2,g1[x] + g2[x]);
    // ans3 = max(ans3,(g1[x] == LLONG_MAX/2?0:g1[x])+(g2[x]==LLONG_MAX/2?0:g2[x]));
}
inline void solve(){
    cin>>n;
    rep(i,1,n-1,1){int u,v;cin>>u>>v;e1.add(u,v,1);e1.add(v,u,1);}
    dfs1(1);dfs2(1,1);
    cin>>q;
    while(q--){
        cin>>k;
        rep(i,1,k,1) cin>>h[i],Q[h[i]] = true;
        build();ans1 = 0,ans3 = 0,ans2 = LLONG_MAX;
        for(auto i:use) f[i] = sz[i] = 0,g1[i] = g2[i] = LLONG_MAX/2;
        dp(1);
        rep(i,1,k,1) rep(j,i+1,k,1) 
            ans2 = min(ans2,0ll+dist[h[j]]+dist[h[i]]-dist[LCA(h[i],h[j])]*2),ans3 = max(0ll+dist[h[i]]+dist[h[j]]-dist[LCA(h[i],h[j])]*2,ans3);
        cout<<ans1<<' '<<ans2<<' '<<ans3<<'\n';
        clear_vtree();
    }
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    solve();
}

标签:dist,g2,fsajakslfkaslf,res,int,edge,e2
From: https://www.cnblogs.com/hzoi-Cu/p/18412684

相关文章