Aimee

正解是树上dp求重心

但是这个迷你范围bfs就行

#include<iostream>
#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
int n,m,k,p;
signed main(){
    scanf("%lld%lld%lld%lld",&n,&m,&k,&p);
    if(p*m<=k){
        int tem=k-p*m;
        if(tem<=(m-1)*(n-p)){
            cout<<"Yes"<<endl;
            for(int i=1;i<=p;++i){
                cout<<m<<" 0"<<endl;
            }
            for(int i=1;i<=n-p;++i){
                if(tem>=m-1){
                    cout<<m-1<<" "<<1<<endl;
                    tem-=(m-1);
                }else{
                    cout<<max((long long)0,tem)<<" "<<m-max((long long)0,tem)<<endl;
                    tem-=(m-1);
                    tem=max(tem,(long long)0);
                }
            }
            return 0;
        }else{
            cout<<"No"<<endl;
            return 0;
        } 
    }else{
        int t=k/p;
        int tem=k-(k/p)*p;
        if(tem<=(t-1)*(n-p)){
            cout<<"Yes"<<endl;
            for(int i=1;i<=p;++i){
                cout<<t<<" "<<m-t<<endl;
            }
            for(int i=1;i<=n-p;++i){
                if(tem>=t-1){
                    cout<<t-1<<" "<<m-t+1<<endl;
                    tem-=(t-1);
                }else{
                    cout<<max((long long)0,tem)<<" "<<m-max((long long)0,tem)<<endl;
                    tem-=(t-1);
                    tem=max(tem,(long long)0);
                }
            }
            return 0;
        }else{
            cout<<"No"<<endl;
            return 0;
        } 
    }
    return 0;
}