Nice problems set:) By the way,does anyone have a better complexity than O(n*m*logm) per testcase for problem 'Sereja and tree 2' ? Is this the intended complexity?

P.S: Ups,I commented in russian section by accident...

Just wondering, did authors have linear (n log MOD) solution for the last problem?

Ps: you know that your post is marked Russian, don't you?

Auto comment: topic has been translated by Sereja (original revision, translated revision, compare)

I really like problemset :) I solved 1st,2nd and 4th task. I had solution for the third, but it gave WA. Can someoe check my solution? Trees aren't my strong side :)

Here is the code:

include

include <stdio.h>

include

include

using namespace std;

const long long mod=1e9+7;

int n,m,t,x,y; long long ans; long long dp[600][30000],a[30000];

vector v[1000],g[30000];

void dfs(int par, int tr)

{

for (int i=0;i<v[tr].size();i++)
    if (v[tr][i]!=par) dfs(tr,v[tr][i]);

    for (int i=1;i<=m;i++)
        a[i]=0;
    for (int i=1;i<=m;i++)
        for (int j=0;j<g[i].size();j++)
        a[g[i][j]]=(a[g[i][j]]+dp[tr][i])%mod;

    for (int i=1;i<=m;i++)
        dp[par][i]=((dp[par][i])*a[i]) % mod;

} int p;

int main()

{

scanf("%d",&t);

for (int i=1;i<=20000;i++) {

p=1;
     while (p*p<i)
      {

          if (i %p==0)

            {
             g[i].push_back(p);
             g[i].push_back(i/p);
      }
      p++;
    }
    if (p*p==i) g[i].push_back(p);
  }

for (int w=0;w<t;w++) {

scanf("%d%d",&n,&m);

  for (int i=1;i<=500;i++)
    for (int j=1;j<=20000;j++)
    dp[i][j]=1;

    for (int i=1;i<=n;i++)
        v[i].clear();

 for (int i=1;i<n;i++)
 {
    scanf("%d%d",&x,&y);
    v[x].push_back(y);
    v[y].push_back(x);
 }

 dfs(0,1);

 ans=0;

 for (int i=1;i<=m;i++)
 ans=(ans+dp[1][i])%mod;

 printf("%lld\n",ans);

}

return 0; }

I have problem to put link of solution.