【树上DP】E - Subtree K-th Max

﹏ヽ暗。殇╰゛Y 2024-03-23 14:16 32阅读 0赞

**一开始的想法是树形DP，然后开始设状态，发现怎么设都不能转移**

**设成第k大，肯定不能转移啊**

**然后除了DP真的就没想法了**

**事实上就是树形DP，只不过它给了小数据，肯定就是暴力维护**

**小数据就是特殊条件，处理方法就是暴力or状压**

**难死我了**

[E - Subtree K-th Max (atcoder.jp)][E - Subtree K-th Max _atcoder.jp]

题意：

![906194ab1b1a49cd9272c7d7bb567dcd.png][]

![cec5f843f9404b5fa96a60b80187f528.png][]

思路：

设一个vector为dp\[u\]，存了以u为树根的子树的前k大的结点编号

然后暴力维护就好了

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    const int mod=1e9+7;
    
    struct ty{
    	int to,next;
    }edge[mxe<<2];
    
    vector<int> dp[mxn];
    int N,Q,u,v,k,tot=0;
    int x[mxn],head[mxn];
    void add(int u,int v){
    	edge[tot].to=v;
    	edge[tot].next=head[u];
    	head[u]=tot++;
    }
    void G_init(){
    	tot=0;
    	for(int i=0;i<=N;i++){
    		head[i]=-1;
    	}
    }
    bool cmp(int x,int y){
    	return x>y;
    }
    void dfs(int u,int fa){
    	dp[u].push_back(x[u]);
    	for(int i=head[u];~i;i=edge[i].next){
    		if(edge[i].to==fa) continue;
    		dfs(edge[i].to,u);
    		for(auto it:dp[edge[i].to]){
    			dp[u].push_back(it);
    		}
    	}
    	sort(dp[u].begin(),dp[u].end(),cmp);
    	while(dp[u].size()>20) dp[u].pop_back();
    }
    void solve(){
    	cin>>N>>Q;
    	G_init();
    	for(int i=1;i<=N;i++) cin>>x[i];
    	for(int i=1;i<=N-1;i++){
    		cin>>u>>v;
    		add(u,v);
    		add(v,u);
    	}
    	dfs(1,0);
    	while(Q--){
    		cin>>u>>k;
    		cout<<dp[u][k-1]<<'\n';
    	}
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[E - Subtree K-th Max _atcoder.jp]: https://atcoder.jp/contests/abc239/tasks/abc239_e
[906194ab1b1a49cd9272c7d7bb567dcd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/6f734fc5863248d481eeab972df1df97.png
[cec5f843f9404b5fa96a60b80187f528.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/67a9de898b6247d28bde48c8313d1458.png