我按照我的AC顺序来写一下吧，A题是个线段树还没有做出来

B-Circle

• 题意已经很清楚了，主要是个人理解的快慢了
• 其实按照这样围成一个环就好了

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;

int main()
{
    int n;
    cin >> n;
    cout << n << endl;

    return 0;
}

D-绝地求生（pubg）

• 调用一下库函数__gcd(x,y) 算出最大公约数t，然后x*y / t

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;

int main()
{
    int t;
    cin >> t;
    for(int i = 1;i <= t;i ++)
    {
        LL x,y;
        cin >> x >> y;

        LL t = __gcd(x,y);

        cout << "Case " << i << ":" << " " << x/t*y << endl;

    }

    return 0;
}

E-悠悠碧波

• 我用的字符串hash暴力做的，首先我是没有提前做出来，是赛后30秒左右才过的
• 只需要找到从大到小找前缀和后缀是不是一样，然后再从中间找到是否存在该前缀，如果存在那么此时就是找到了最大值然后break

#include <iostream>
#include <cstring>
using namespace std;

const int N = 100010 ,P = 131;

typedef unsigned long long ull;

int n, m;
char str[N];
ull h[N],p[N];

ull get(int l,int r)
{
    return h[r] - h[l-1] * p[r-l+1];
}

bool solve(int l)
{
   for(int i = 2;i <= n - l;i ++)
   {
       if(get(i,i + l - 1) == get(1,l)){
          return true;
       }
   }
   return false;
}

int main()
{
    cin >> str + 1;
    p[0] = 1;
    n = strlen(str + 1);
    for(int i = 1;i <= n;i++)
    {
        h[i] = h[i-1] * P + str[i];
        p[i] = p[i-1] * P;
    }
    int i,j;

    for(i = n - 1,j = 2;i > 0;i --,j ++)
    {
        if(get(1,i) == get(j,n)){

            if(solve(i))
            {
                for(int j = 1;j <= i;j ++)
                {
                    cout << str[j];
                }
                break;
            } 

        }
    }

    return 0;
}

• 接下来是我在赛后补的C题了，这个题非常好，建议大家去做一下

  C-Tree

• 这个题涉及到了费马小定理，换根Dp
• 题意比较晦涩难懂
• 求一颗树中每个点包含其的联通子集的数量
• 首先还是按照换根dp的套路，以1号点为根节点算出每个点对其父亲节点的贡献度
• 而每个点对其父亲的贡献度为 base = base * (p[x] + 1) % mod;
• p[u] = base
• 这个是根据乘法原理推出来的

  void dfs1(LL u,LL fa)
  {
    pre[u] = fa;
    LL base = 1;
    for(auto &x : v[u])
    {
        if(x == fa)continue;
        dfs1(x,u);
        base = base * (p[x] + 1) % mod;
    }
    p[u] = base;
  }

• 下面就是dfs2了，也就是换根的公式了
• 对于每个子节点x其ans[x] = (ans[u] / (p[x] + 1) + 1) * p[x] % mod;
• 这里ans[u]是父亲的值，那么父亲所收获的除了x节点的贡献度不就是,那么其他节点对x的贡献度不就是,那么x的其他节点对x的贡献度就是p[x]，所以
• 而在算num的时候我们需要做除法并且需要%mod,那么这个时候就涉及到了求逆元
• %%
• %

            LL num = (long long)ans[u] * inv(p[x] + 1) % mod;
            ans[x] = (num + 1) * (p[x]) % mod;

• 但是如果p[x] + 1 % mod = 0 ，那么逆元就求不出来了，这个时候我们需要找到一个新的道路来求出ans[x]
• 我们需要算出其父亲节点u对x的贡献度，那么也就是算出父亲节点的所有不包括子节点x的贡献度
• u的父亲节点对u的贡献度为 num = ans[fa] * inv(p[u] + 1) % mod
• u的其他节点对u的贡献度就是num = num * (p[y] + 1) % mod
• 那么u对x的贡献度不就是num + 1
• 所以ans[x] = (num + 1) * p[x] % mod

            LL num = ans[fa] * inv(p[u] + 1) % mod + 1;
            for(auto &y : v[u])
            {
                if(y == x || y == fa)continue;
                num = num * (p[y] + 1) % mod;
            }
            ans[x] = (num + 1) * p[x] % mod;

• 下面是这个题AC的代码

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long LL;
const LL N = 1e6 + 10;
const LL mod = 1e9 + 7;

vector<LL>v[N];

LL p[N];
LL ans[N];
LL n;

LL qpow(LL a,LL k)
{
    LL res = 1;
    while(k)
    {
        if(k & 1)
            res = (long long)res * a % mod;
        a = (long long )a * a % mod;
        k >>= 1;
    }
    return res;
}

LL inv(LL x)
{
    return qpow(x,mod - 2) % mod;
}

void dfs1(LL u,LL fa)
{
    LL base = 1;
    for(auto &x : v[u])
    {
        if(x == fa)continue;
        dfs1(x,u);
        base = base * (p[x] + 1) % mod;
    }
    p[u] = base;
}


void dfs2(LL u,LL fa)
{
    for(auto &x : v[u])
    {
        if(x == fa)continue;

        if((p[x] + 1) % mod == 0)
        {
            LL num = ans[fa] * inv(p[u] + 1) % mod + 1;
            // 这是算出u的父亲节点对u的贡献度，这个父亲是fa

            for(auto &y : v[u])
            {
                if(y == x || y == fa)continue;
                /*
                    对于这个地方是算除去x节点（fa是因为上面我已经算了，所以不需要再算了），
                    的其他节点对u的贡献度;(此时最好自己假象如果x的父亲的话，该怎么求，就好理解了)
                */
                num = num * (p[y] + 1) % mod;
            }
            ans[x] = (num + 1) * p[x] % mod;
        }
        else
        {
            LL num = (long long)ans[u] * inv(p[x] + 1) % mod;
            ans[x] = (num + 1) * (p[x]) % mod;
        }

        dfs2(x,u);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for(LL i = 0;i < n - 1;i ++)
    {
        LL a,b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    dfs1(1,0);

    ans[1] = p[1];

    dfs2(1,0);
    // exit(0);
    for(LL i = 1;i <= n;i ++)
    {
        cout << ans[i] << endl;
    }


    return 0;
}

• 如果哪里不对希望大佬指正