A. Star Trek

This is an Euletta question.

Because the title says that only $2$edges go once, the remaining $m-2$edges go twice,

Split this $m$two-way edge into $2$one-way edges,

The end result is to delete the two edges and make the remaining broken edges an Euler Road, (but not expected in the exam.))

Euler's Road means walking all sides once from the start of $S$to the end of $T$, $T$can be different from $S$.

In a directed graph, Euler's rule is that there are only $0 or $2 points with unequal degrees of exit and entry.

Simply enumerate each point $i$, select two edges to delete from all its edges, and both edges must have a starting point of $i$and an ending point of $i$.

Contribution to the answer is $\frac {n\times(n-1)}{2}$

As to why you're dividing by $2, take a closer look at the question. The essence of the path is different.

Then there is the contribution of the self-loop.

In addition, the title does not mention connectivity, so the connectivity of the whole picture should be determined.

If there are multiple subgraphs and more than one of them contains more than or equal to $1$,

Then the number of scenarios must be $0$.

Ugly code:

#include<iostream>
#include<cstring>
#include<cstdio>
#define Maxn 500050
#define Reg register
using namespace std;
int n,m,tot,zh,nmp,fat[Maxn],fir[Maxn],vis[Maxn],num[Maxn];
long long ans;
struct Tu {int st,ed,next;} lian[Maxn*100];
void add(int x,int y)
{
    lian[++tot].st=x;
    lian[tot].ed=y;
    lian[tot].next=fir[x];
    fir[x]=tot;
    return;
}
int getf(int x)
{
    if(fat[x]==x) return x;
    else return fat[x]=getf(fat[x]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(Reg int i=1,x,y;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        if(x==y) ++zh;
        else add(x,y),add(y,x);
    }
    for(Reg int i=1,p;i<=n;++i) fat[i]=i;
    for(Reg int i=1;i<=tot;++i)
    {
        int p=getf(lian[i].st);
        int q=getf(lian[i].ed);
        if(p!=q) fat[p]=q;
    }
    for(Reg int i=1;i<=n;++i)
    {
        int p=getf(i);
        ++num[p];
        if(!vis[p])
        {
            vis[p]=1;
            ++nmp;
        }
    }
    for(Reg int i=1,p;i<=n;++i)
    {
        p=0;
        for(Reg int j=fir[i];j;j=lian[j].next) ++p;
        ans+=(long long)p*(p-1)/2;
    }
    if(zh)
    {
        ans+=(long long)zh*(m-zh);
        ans+=(long long)zh*(zh-1)/2;
    }
    if(nmp==1) printf("%lld",ans);
    else
    {
        int ok=0;
        for(Reg int i=1;i<=n;++i)
            if(num[i]>=2) ++ok;
        if(ok==1) printf("%lld",ans);
        else printf("0");
    }
    return 0;
}

 

 

B. Cutting down trees

It is easy to get a formula that meets the requirements of the title:

$\sum \lceil \frac{a_i}{d}\rceil \times d-\sum a_i \leq k$

Move this thing over and simplify it to get:

$\sum \lceil \frac{a_i}{d}\rceil\leq \lfloor \frac{k+\sum a_i}{d}\rfloor$

Write $k+\sum a_i$as $C$,

So the original is $\sum \lceil \frac{a_i}{d}\rceil\leq \lfloor \frac{C}{d}\rfloor$

The formula on the right can be partitioned using number theory (although I'm not sure)

The equations on the right are piecewise, that is, their values do not change within a certain interval.

If you know the left endpoint, the right endpoint can be calculated, and this formula looks like this: $R=\left\lfloor\frac{C}{\lfloor\frac{C}{L}\rfloor}\rightrfloor$.

The formula on the left is monotonic and decreases as $d increases.

Then, within each interval, if there is a $d$value that does not satisfy the upper formula, it is certainly not valid if it is less than $d$

And what we're looking for is the maximum of $d$so all we need to do is determine if each right endpoint is legal.

If legal, update the answer, otherwise $break$, you don't need to continue judging other values in this interval.

The time complexity of such a method is $O(n\sqrt {n})$

Ugly code:

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define min(x,y) ((x)<(y)?(x):(y))
#define Maxn 1050
#define Reg register
using namespace std;
long long n,k,ans,C,maxx;
long long num[Maxn];
bool judge(long long x,long long P)
{
    long long anp=0;
    for(Reg int i=1;i<=n;++i)
    {
        if(num[i]%x==0) anp+=num[i]/x;
        else anp+=(num[i]/x+1);
        if(anp>P) return 0;
    }
    if(anp>P) return 0;
    else return 1;
}
int main()
{
    long long P;
    scanf("%lld%lld",&n,&k); C=k;
    for(Reg int i=1;i<=n;++i)
    {
        scanf("%lld",&num[i]);
        maxx=max(maxx,num[i]);
        C+=num[i];
    }
    long long l=1,r=1;
    while(l<=maxx+k)
    {
        r=C/(C/l); P=C/l;
        if(judge(min(r,maxx+k),P)) ans=min(r,maxx+k);
        l=r+1;
    }
    printf("%lld",ans);
    return 0;
}

 

 

 

 

C. Super Tree

$wd$Dashen Blog, Portal.

Ugly code:

#include<iostream>
#include<cstring>
#include<cstdio>
#define Maxn 3050
#define max(x,y) ((x)>(y)?(x):(y))
#define Reg register
using namespace std;
long long sum,n,mod,dp[Maxn][Maxn];
int main()
{
    scanf("%lld%lld",&n,&mod);
    dp[1][1]=dp[1][0]=1;
    for(Reg int i=1;i<=n-1;++i)
    {
        for(Reg int j=0;j<=n-i+2;++j)
        {
            for(Reg int k=0;k<=n-i+2-j;++k)
            {
                sum=(dp[i][j]*dp[i][k])%mod;
                dp[i+1][j+k]=(dp[i+1][j+k]+sum)%mod;
                //choose j+k Contributions selected by left and right paths
                dp[i+1][j+k+1]=(dp[i+1][j+k+1]+sum)%mod;
                //choose j+k+1 Select left and right paths respectively+Contribution of Root Selection
                dp[i+1][j+k]=(dp[i+1][j+k]+sum*2*(j+k))%mod;
                //choose j+k Contribution of a left (and right) edge (start or end) to the root
                if(j+k-1>=0) dp[i+1][j+k-1]=(dp[i+1][j+k-1]+sum*j*k*2)%mod;
                //choose j+k-1 Path Left (Right) Choose an Edge-to-Root Right (Left) Contribution
                if(j+k-1>=0) dp[i+1][j+k-1]=(dp[i+1][j+k-1]+sum*(j*j-j+k*k-k))%mod;
                //choose j+k-1 Contribution of a path from left (right) to root to left (right)
            }
        }
    }
    printf("%lld",dp[n][1]%mod);
    return 0;
}

 

 

summary

$T1$Unexpected Euler circuit, first reduced by a point with $tarjan$

The first thing that came to mind in the examination room was that $tarjan$had been reduced to a forest.

For each node of the forest, select $2 on the edge that connects it and update it like this.

The final judgment is from rings, $2$self rings, $1$self rings, $1$edges.

Then if there are more than $2$edges in the ring of the leaf node on the tree, it will only contribute $2$. (I don't know what to think at that time)

Last count $ans$output.

$T2$Two points when you see this question.

Coded twice, the sample passed directly, I thought I was right, I didn't expect it to be monotonic.

The last $20 points (but everyone else's two points are $30$...)

$T3$No idea,

You hit $dfs$once, ran to $4$, and then started running $5 for about half an hour.

That cheats you $15.

Last $0+20+15=35$.(Question 1, $cout<$0, $20 and I exploded zero)

Nothing good.