题目链接

长春花

解题思路

放在第一题，应该是签到题的地位，我们先打个暴力开始找规律，可以发现，当p$ \leq 10^5$时，答案最多不超过$40$（大概？），那么我们直接暴力枚举答案即可。

紫罗兰

解题思路

把题意翻译一下就是找最小环的个数，比赛的时候脑抽了，写了个异或哈希（为了判断环不重复），同时找环的时候又用了麻烦的方法。

实际上在对于每一个点进行bfs时，从一个点开始扩展时遇到另一个已经扩展过的点就说明现在已经找到了环，那么我们就可以直接开始统计。由于环上每一个点开始找环都会记一次，所以我们最后将答案除以环的长度即可，需要注意的是，当环的长度为奇数时，答案需要额外再除以2，至于为什么，个人建议当环的长度为$3$时，读者自己模拟一下。

#include <bits/stdc++.h>
#define int long long 
using namespace std;

const int N=1e5+10;

int e[N],ne[N],h[N],idx;

int n,m;
int ans;
int res=0x3f3f3f3f;
int d[N];
int w[N];

void add(int x,int y){
    e[++idx]=y;
    ne[idx]=h[x];
    h[x]=idx;
}

void bfs(int s){
    for(int i=1;i<=n;i++) d[i]=0x3f3f3f3f;
    d[s]=0;
    for(int i=1;i<=n;i++){
        w[i]=0;
    }
    w[s]=1;
    queue<int> q;
    q.push(s);
    while(q.size()){
        int x=q.front();
        // int la=q.front().second;
        q.pop();
        for(int i=h[x];i;i=ne[i]){
            int y=e[i];
            // if(y==la) continue;
            if(d[y]==d[x]||d[y]==d[x]+1){
                if(res>d[x]+d[y]+1){
//                    cout<<res<<'\n';
//                    cout<<d[x]<<' '<<d[y]<<' '<<1<<'\n';
                    res=d[x]+1+d[y];
//                    cout<<res<<'\n';
                    ans=w[x]*w[y];
                }
                else if(res==d[x]+1+d[y]){
                    ans+=w[x]*w[y];
                }
            }
            if(d[y]>d[x]+1){
                d[y]=d[x]+1;
                w[y]=w[x];
                q.push(y);
            }
        }
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    for(int i=1;i<=n;i++){
        bfs(i);
    }
//    cout<<res<<'\n';
    if(res%2){
        ans/=res;
        ans/=2;
    }
    else {
        ans/=res;
    }
    cout<<ans<<'\n';
    return 0;
}

/*
4 5
1 2
1 3
1 4
2 4
3 4
*/

/*
1000 15
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6
*/

/*

1000 1
1 2

*/

天竺葵

解题思路

这一题与曾经的一道模拟赛的题很像，但是不幸的是并不能直接套用那一题的做法，考场上写了个加的贪心做法。但性质都是一样的。

性质：对于一颗最小生成树而言，非树边一定可以与树上的边组成一个环，并且该非树边的权值应当比环中的数边要大。

根据这个性质，我们可以缩小非树边的取值范围，最后再进行贪心的对全部的边进行赋值。如果不能赋值，则代表无解。

这里我原先想的是直接在贪心赋值的同时找到那个环，然后优先给环上的树边赋完值后直接给非树边赋值，但这是错误的。因为给非树边赋值后，可能使得后面的边的赋值取不到范围内的数，所以是错的解法。

#include <bits/stdc++.h>
#define PII pair<int,int>

using namespace std;

const int N=5e5+10;
const int M=20;

int a[N],dep[N],ans[N];
int fa[N][M],an[N][M];

vector<int> del[N];

vector<PII > to[N];

multiset<int> se[N];

priority_queue<PII,vector<PII >,greater<PII > > q;

struct node{
    int x,y,l,r,id;
}e[N];

void clear(int n){
    for(int i=1;i<=n;i++){
        to[i].clear(),del[i].clear(),se[i].clear();se[i].insert(1e9);
        while(q.size()) q.pop();
    }
}
void init(int x,int f){
    fa[x][0]=f;dep[x]=dep[f]+1,an[x][0]=e[a[x]].l;
    for(int i=1;i<M;i++){
        fa[x][i]=fa[fa[x][i-1]][i-1];
        an[x][i]=max(an[x][i-1],an[fa[x][i-1]][i-1]);
    }
    for(int i=0;i<to[x].size();i++){
        PII y=to[x][i];
        if(y.first!=f){
            a[y.first]=y.second,init(y.first,x);
        }
    }
}

void dfs(int x,int fa){
    for(int i=0;i<to[x].size();i++){
        if(to[x][i].first==fa) continue;
        int y=to[x][i].first;
        dfs(y,x);
        if(se[y].size()>se[x].size()) swap(se[y],se[x]);
        se[x].insert(se[y].begin(),se[y].end());
    }
    for(int i=0;i<del[x].size();i++){
        int y=del[x][i];
        se[x].erase(se[x].find(y));
    }
    e[a[x]].r=min(e[a[x]].r,(*se[x].begin())-1);
}

int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=M-1;i>=0;i--){
        if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
    }
    if(x==y) return x;
    for(int i=M-1;i>=0;i--){
        if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    }
    return fa[x][0];
}

int get(int x,int y){
    if(x==y) return -1e9;
    int ans=-1e9;
    for(int i=M-1;i>=0;i--){
        if(dep[fa[x][i]]>dep[y]) ans=max(ans,an[x][i]),x=fa[x][i];
    }
    return max(ans,an[x][0]);
}

bool cmp(node a,node b){
    return a.l<b.l;
}

void solve(){
    int n,m;
    cin>>n>>m;
    clear(n);
    for(int i=1;i<=m;i++){
        cin>>e[i].x>>e[i].y>>e[i].l>>e[i].r;
        e[i].id=i;
    }
    for(int i=1;i<n;i++){
        to[e[i].x].push_back({e[i].y,i});
        to[e[i].y].push_back({e[i].x,i});
    }
    init(1,0);
    for(int i=n;i<=m;i++){
        int r=lca(e[i].x,e[i].y);
        e[i].l=max(e[i].l,max(get(e[i].x,r)+1,get(e[i].y,r)+1));
        se[e[i].x].insert(e[i].r);
        se[e[i].y].insert(e[i].r);
        del[r].push_back(e[i].r);
        del[r].push_back(e[i].r);
    }
    dfs(1,0);
    sort(e+1,e+1+m,cmp);
    for(int i=1,j=1;i<=m;i++){
        while(j<=m&&e[j].l<=i) q.push({e[j].r,e[j].id}),++j;
        if(q.empty()) return void(cout<<"NO\n");
        PII y=q.top();
        q.pop();
        if(y.first<i) return void(cout<<"NO\n");
        ans[y.second]=i;
    }
    cout<<"YES\n";
    for(int i=1;i<=m;i++){
        cout<<ans[i]<<' ';
    }
    cout<<'\n';

}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

风信子

解题思路

根据lxl讲，这是道人类智慧题，显然，我们在$ n \leq 6 and m \leq 6$ 的情况下可以暴搜求解，那么其他的情况都可以通过某种构造来使得范围逐渐变小到上述范围。好像是个大模拟，代码复杂极强，写不了。