zcmimi's blog
查看原题

点击跳转

先来考虑普通的树型dp怎么做

SZ_x表示x的子树中有多少个查询点,d_x表示x的深度

  1. 这些新通道的代价和

    考虑每条边要被统计多少次:

    假设yx的某个子节点,x\leftrightarrow y会被统计(k-SZ_y)\times SZ_y次,

    (起点可以是y的子树中任一查询点,终点可以是y子树外的任一查询点,这样的话路径必然经过x\leftrightarrow y)

    那么贡献是(d_y-d_x)\times (k-SZ_y)\times SZ_y

  2. 这些新通道中代价最小/大的是多少

    有点类似树型dp求树的直径

    x的子树中最长的路径是: 子树中深度最大的查询点的深度+子树中深度次大的查询点的深度(若x是查询点则包括x\leftrightarrow x,深度为0)

    最短路径和上面的求法类似

套上虚树就可以解决这道题了

如果不懂的话就看代码咯

#include<bits/stdc++.h>
#pragma GCC optimize(3)
#define il __inline__ __attribute__ ((always_inline))
typedef long long ll;
#define ll long long
#define rg register
#define For(i,x,y) for(int i(x);i<=y;++i)
#define fl(i,x) for(int i(head[x]),to;to=e[i].to,i;i=e[i].nxt)
il int MAX(int x,int y){return x>y?x:y;}
il int MIN(int x,int y){return x<y?x:y;}
namespace IO{const int str=1<<20;static char in_buf[str],*in_s,*in_t;bool __=0;il char gc(){return (in_s==in_t)&&(in_t=(in_s=in_buf)+fread(in_buf,1,str,stdin)),in_s==in_t?__=1,EOF:*in_s++;}template<typename T>il void in(T &x){if(__)return;rg char c=gc();bool f=0;while(c!=EOF&&(c<'0'||c>'9'))f^=(c=='-'),c=gc();if(c==EOF){__=1;return;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=x*10+c-48,c=gc();if(c==EOF)__=1;if(f)x=-x;}static char out_buf[str],*out_s=out_buf,*out_t=out_buf+str;il void flush(){fwrite(out_buf,1,out_s-out_buf,stdout);out_s=out_buf;}il void pt(char c){(out_s==out_t)?(fwrite(out_s=out_buf,1,str,stdout),*out_s++=c):(*out_s++=c);}template<typename T>il void out(T x){if(!x){pt('0');return;}if(x<0)pt('-'),x=-x;char a[50],t=0;while(x)a[t++]=x%10,x/=10;while(t--)pt(a[t]+'0');}}using namespace IO;
const int N=1000011,inf=1000000007;
int n,k,cnt=0,head[N];
struct edge{int to,nxt;}e[N<<1];
il void add(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;}
int siz[N],top[N],f[N],d[N],dfn[N],sz=0;
void dfs(int x){
    siz[x]=1;dfn[x]=++sz;
    fl(i,x)if(to!=f[x]){
        f[to]=x;
        d[to]=d[x]+1;
        dfs(to);
        siz[x]+=siz[to];
    }
}
void bt(int x,int tp){
    top[x]=tp;int k=0;
    fl(i,x)if(to!=f[x]&&siz[to]>siz[k])k=to;
    if(k)bt(k,tp);
    fl(i,x)if(!top[to])bt(to,to);
}
il int lca(int x,int y){
    while(top[x]!=top[y])
        d[top[x]]>d[top[y]]?x=f[top[x]]:y=f[top[y]];
    return d[x]<d[y]?x:y;
}
int a[N],st[N],tp,SZ[N],mx_d[N],mi_d[N],a1,a2;
ll ans;
bool v[N];
il bool cmp(int x,int y){return dfn[x]<dfn[y];}
void dp(int x){
    if(v[x])SZ[x]=1,mx_d[x]=d[x],mi_d[x]=d[x];
    else    SZ[x]=0,mx_d[x]=-inf,mi_d[x]=inf;
    int p1=-inf,p2=-inf,q1=inf,q2=inf;
    fl(i,x){
        dp(to);

        mx_d[x]=MAX(mx_d[x],mx_d[to]);
        if(mx_d[to]>=p1)p2=p1,p1=mx_d[to];
        else p2=MAX(p2,mx_d[to]);

        mi_d[x]=MIN(mi_d[x],mi_d[to]);
        if(mi_d[to]<=q1)q2=q1,q1=mi_d[to];
        else q2=MIN(q2,mi_d[to]);

        ans+=1ll*(k-SZ[to])*SZ[to]*(d[to]-d[x]);
        SZ[x]+=SZ[to];
    }
    a1=MIN(a1,q1+q2-2*d[x]);
    if(v[x])a1=MIN(a1,q1-d[x]);

    a2=MAX(a2,p1+p2-2*d[x]);
    if(v[x])a2=MAX(a2,p1-d[x]);
    head[x]=0;
}
int main(){
    in(n);
    int q,x,y,t;
    For(i,1,n-1)in(x),in(y),add(x,y),add(y,x);
    d[1]=1;dfs(1);bt(1,1);
    cnt=0;memset(head,0,sizeof head);
    in(q);
    while(q--){
        in(k);
        For(i,1,k)in(a[i]),v[a[i]]=1;
        std::sort(a+1,a+k+1,cmp);
        cnt=0;st[tp=1]=1;
        For(i,1,k){
            x=a[i];t=lca(x,st[tp]);
            while(d[t]<d[st[tp]]){
                if(d[t]>=d[st[tp-1]]){
                    add(t,st[tp--]);
                    if(t!=st[tp])st[++tp]=t;
                    break;
                }
                add(st[tp-1],st[tp]),--tp;
            }
            if(st[tp]!=x)st[++tp]=x;
        }
        while(tp>1)add(st[tp-1],st[tp]),--tp;
        ans=0;a1=inf,a2=0;
        dp(1);
        out(ans),pt(' '),out(a1),pt(' '),out(a2),pt('\n');
        For(i,1,k)v[a[i]]=0;
    }
    flush();
}
LG 4103 [HEOI2014]大工程
comment评论
Search
search