Džumbus

考场的思路。本来想先把子任务 12 的链式情况打了，然后再来打树形的。结果子任务 12 都没有调过。

不是，我 T2 subtask12 过了呀，我为什么三分钟后还会交一次呢？这真的是让我炸肛了啊！！！！

思路

根据然而，这 M 组朋友不可能将 A 分享给别人的答案重新分享给 A。可知，本题是不会存在环的。

然后又根据 M<N 可知，本题可能存在多棵树。

子任务 12

每个点最多与两个点相连，那么就说明子任务 12 是一条链。很明显。我们设计 DP 为 f_{i,j,0/1,0/1}。表示到第 i 个数为止，共有 j 人会分享答案，其中第 i 人饮不饮酒时的最小值。

那么我们要先将每个人在链上具体的位置求出来。

很明显，此时的转移为：

• 如果第 i 个人不饮酒，那么对答案肯定没贡献，转移就为 f_{i,j,0}=\min(f_{i-1,j,0},f_{i-1,j,1})。
• 第 i 个人饮酒，分情况讨论。
  • 如果第 i-1 个人不饮酒，此时 i 没办法分享答案，则 f_{i,j,1}=\min(f_{i,j,1},f_{i-1,j,0}+d_{i})。
  • 或者要令第 i 个人会分享，则 f_{i,j,1}=\min(f_{i,j,1},f_{i-1,j-2,0}+d_{i}+d_{i-1})。
  • 如果第 i-1 要饮酒，那么第 i 个人肯定会分享答案。则 f_{i,j,1}=\min(f_{i,j,1},f_{i-1,j-1,1}+d_{i})。

最后记 val_{x} 为有 x 个人会分享答案时的最小饮酒量。

对于对于每个询问找满足答案的最大值即可。

代码中多加了一维，考虑了饮酒后对答案有无贡献，感觉思路会更加的清晰，反正内存大。

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

const int N=1010;
const int Que=2e5+10;
const int INF=0x3f3f3f3f;

typedef long long ll;
typedef pair<int,int> pii;

int n,m;

int d[N];
pii s[Que];
int ans[Que]; 
ll f[N][N][2][2];//他本身有没有被计入答案 

int root=1;
int dep[N],din[N];

vector<int> e[N];

void add(int u,int v){
    e[u].push_back(v);
}//end

int p[N];

void bfs(){
    memset(dep,INF,sizeof dep);
    dep[root]=1;dep[0]=0;
    queue<int> q;
    q.push(root);
    while(q.size()){
        int x=q.front(); q.pop();
        for(int y:e[x]){
            if(dep[y]>dep[x]+1){
                dep[y]=dep[x]+1;
                q.push(y);
            }
        }   
    }
    for(int i=1;i<=n;i++) p[dep[i]]=i;
}//end

ll val[N];

int main(){
    freopen("dzumbus.in","r",stdin);
    freopen("dzumbus.out","w",stdout);

    ios::sync_with_stdio(0);

    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>d[i];
    for(int i=1;i<=m;i++){
        int a,b; cin>>a>>b;
        din[a]++; din[b]++;
        add(a,b); add(b,a);     
    }

    for(int i=1;i<=n;i++) {
        if(din[i]==1){
            root=i;
            break;
        }
    }

    bfs();

    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            f[i][j][0][0]=f[i][j][1][0]=1e18;
            f[i][j][0][1]=f[i][j][1][1]=1e18;
        }
    }

    f[0][0][0][0]=0;

    for(int i=1;i<=n;i++){
        int x=p[i];
        for(int j=0;j<=i;j++){
            f[i][j][0][0]=min(f[i-1][j][0][0],min(f[i-1][j][1][0],f[i-1][j][1][1]));
            f[i][j][1][0]=min(f[i][j][1][0],f[i-1][j][0][0]+d[x]);
            if(j>=2) f[i][j][1][1]=min(f[i][j][1][1],f[i-1][j-2][1][0]+d[x]);
            if(j) f[i][j][1][1]=min(f[i][j][1][1],f[i-1][j-1][1][1]+d[x]);
        }
    }

    for(int j=0;j<=n;j++){
        val[j]=1e18;
        for(int i=1;i<=n;i++){
            for(int k=0;k<2;k++){
                val[j]=min(val[j],min(f[i][j][1][k],f[i][j][0][k]));
            }   
        }
    }

    int t; cin>>t;
    for(int i=1;i<=t;i++){
        int x; cin>>x;
        int tp=0;
        for(int i=1;i<=n;i++){
            if(val[i]<=x) tp=i;
        }
        cout<<tp<<endl; 
    }

}//end

正解

考虑将 DP 策略带入到树上。

因为这个图可能为森林，所以我们建一个超级源点。

此时设计 DP 状态为 f_{i,j,0/1/2}，表示的是到第 i 个人（只看 i 子树内的情况），有几个人选了，他本身 不选 / 选了但是没有贡献 / 选了并且有贡献。

那么转移只需要转移到树上即可。

正解代码

被卡常了，所以把 subtask2 也加上了，代码稍显臃肿。

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

const int N=1010;
const int Que=2e5+10;
const int INF=0x3f3f3f3f;

typedef long long ll;
typedef pair<int,int> pii;

int n,m;

int d[N];
pii s[Que];
int ans[Que]; 

int root=1;
int dep[N],p[N];

int fa(int x){
    if(p[x]==x) return x;
    return p[x]=fa(p[x]);
}//end

vector<int> e[N];

void add(int u,int v){
    e[u].push_back(v);
}//end

ll val[N];
int sz[N];
ll f[N][N][3];//他本身有没有被计入答案 

void dfs(int x,int fa){ 
    sz[x]=1;
    f[x][0][0]=0,f[x][0][2]=d[x];
    for(int y:e[x]) {
        if(y==fa) continue;
        dfs(y,x);
        sz[x]+=sz[y];
        for(int i=sz[x];i>=0;--i) {
            for(int j=min(sz[y],i);j>=0;--j) {
                f[x][i][0]=min(f[x][i][0],f[x][i-j][0]+min({f[y][j][0],f[y][j][1],f[y][j][2]}));
                f[x][i][1]=min(f[x][i][1],f[x][i-j][1]+min(f[y][j][0],f[y][j][1]));
                f[x][i][2]=min(f[x][i][2],f[x][i-j][2]+f[y][j][0]);
                if(i-j>=2) f[x][i][1]=min(f[x][i][1],f[x][i-j-2][2]+f[y][j][2]);
                if(i-j>=1) {
                    f[x][i][1]=min(f[x][i][1],f[x][i-j-1][1]+f[y][j][2]);
                    f[x][i][1]=min(f[x][i][1],f[x][i-j-1][2]+f[y][j][1]);
                }
            }
        }
    }   
}//end

void bfs(){
    memset(dep,INF,sizeof dep);
    dep[root]=1;dep[0]=0;
    queue<int> q;
    q.push(root);
    while(q.size()){
        int x=q.front(); q.pop();
        for(int y:e[x]){
            if(dep[y]>dep[x]+1){
                dep[y]=dep[x]+1;
                q.push(y);
            }
        }   
    }
    for(int i=1;i<=n;i++) p[dep[i]]=i;
}//end

int din[N];

void subtask2(){
    for(int i=1;i<=n;i++) {
        if(din[i]==1){
            root=i;
            break;
        }
    }
    bfs();
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            f[i][j][0]=f[i][j][1]=f[i][j][2]=1e18;
        }
    }
    f[0][0][0]=0;
    for(int i=1;i<=n;i++){
        int x=p[i];
        for(int j=0;j<=i;j++){
            f[i][j][0]=min(f[i-1][j][0],min(f[i-1][j][1],f[i-1][j][2]));
            f[i][j][1]=min(f[i][j][1],f[i-1][j][0]+d[x]);
            if(j>=2) f[i][j][2]=min(f[i][j][2],f[i-1][j-2][1]+d[x]);
            if(j) f[i][j][2]=min(f[i][j][2],f[i-1][j-1][2]+d[x]);
        }
    }
    for(int j=0;j<=n;j++){
        val[j]=1e18;
        for(int i=1;i<=n;i++){
            for(int k=0;k<3;k++){
                val[j]=min(val[j],f[i][j][k]);
            }   
        }
    }   
    int t; cin>>t;
    for(int i=1;i<=t;i++){
        int x; cin>>x;
        int tp=0;
        for(int i=1;i<=n;i++){
            if(val[i]<=x) tp=i;
        }
        cout<<tp<<endl; 
    }   
    exit(0);
}//end

int main(){
    freopen("dzumbus.in","r",stdin);
    freopen("dzumbus.out","w",stdout);

    ios::sync_with_stdio(0);

    cin>>n>>m;

    int tot=n;
    for(int i=1;i<=n;i++) p[i]=i;

    for(int i=1;i<=n;i++) cin>>d[i];
    for(int i=1;i<=m;i++){
        int a,b; cin>>a>>b;
        add(a,b); add(b,a);     
        din[a]++,din[b]++;
        if(din[a]==2) tot--;
        if(din[b]==2) tot--;
        int pa=fa(a),pb=fa(b);
        if(pa==pb) continue;
        p[pa]=pb;
    }

    if(tot==2) subtask2();

    for(int i=1;i<=n;i++) {
        if(fa(i)==i){
            add(n+1,i);
            add(i,n+1);//和虚拟源点建立联系 
        }
    }   

    for(int i=0;i<=n+1;i++){
        for(int j=0;j<=n;j++){
            f[i][j][1]=f[i][j][0]=f[i][j][2]=1e18;
        }
    }

    dfs(n+1,0); 

    val[n+1]=1e18;
    for(int i=n;i;--i) {
        val[i]=min(val[i+1],f[n+1][i][0]); 
    }

    int t; cin>>t;
    for(int i=1;i<=t;i++){
        int x; cin>>x;
        int tp=upper_bound(val+1,val+n+1,x)-val-1;
        cout<<tp<<endl;
    }

}//end