---
tags: IOICamp
---

# Day2 個人賽

:::spoiler Description
:::

:::spoiler Scoreboard
:::

:::spoiler pA**
:::

:::spoiler pB**
:::

:::spoiler pC
:::

:::spoiler pD
:::

:::spoiler pE
:::

:::spoiler pF*
:::

:::spoiler pG**
:::

---

[TOC]

#### **pA. 序列圖**

#### **pB. 小 Y 與小 P**

#### **pC. 小風愛塗色**

:::spoiler Solution (joylintp)

#include<bits/stdc++.h>
#pragma gcc optimize("Ofast")
#define MOD 1000000007

using namespace std;

long long k, ans[200001];
set<int> edge[200001];

int dfs(int x)
{
    if (ans[x])
        return ans[x];

    if (edge[x].empty())
        return ans[x] = k;
    if (edge[x].size() == 1)
    {
        int c = *edge[x].begin();
        edge[c].erase(x);
        return ans[x] = dfs(c) * k % MOD;
    }

    ans[x] = 1;
    for (int i : edge[x])
    {
        edge[i].erase(x);
        ans[x] = (ans[x] + dfs(i) - 1) % MOD;
    }
    return ans[x] = ans[x] * k % MOD;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, a, b;
    cin >> n >> k;
    for (int i = 1; i < n; i++)
        cin >> a >> b, edge[a].insert(b), edge[b].insert(a);
    dfs(1);
    cout << ans[1] << '\n';

    return 0;
}

:::

:::spoiler Solution (SorahISA)

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

#define IOS() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define X first
#define Y second
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
#define Push push_back

using lli = long long;
using pii = pair<int, int>;
using pll = pair<lli, lli>;
using Double = long double;
template<typename T>
using Vector = vector<vector<T>>;
template<typename T>
using Prior = priority_queue<T>;
template<typename T>
using prior = priority_queue<T, vector<T>, greater<T>>;

const lli mod = 1E9 + 7;
const Double PI = 3.1415926535846;
const Double eps = 1e-8;

const int maxn = 2E5 + 5;

vector<int> adj[maxn];
lli n, k;

lli dfs(int now, int lst) {
    lli tmp = 0; // sum of child
    for (auto x : adj[now]) {
        if (x != lst) {
            tmp += dfs(x, now);
        }
    }
    
//  cout << "now on " << now << "\n    ";
    if (adj[now].size() == 1) {
//      cout << "return " << k << "\n";
        return k;
    }
    else {
//      cout << "return " << k * (tmp - (adj[now].size() - 1) + 1) % mod << "\n";
        return k * (tmp - (adj[now].size() - 1) + 1) % mod;
    }
}

void solve() {
    int u, v;
    cin >> n >> k;
    
    adj[1].Push(0);
    for (int i = 0; i < n-1; ++i) {
        cin >> u >> v;
        adj[u].Push(v);
        adj[v].Push(u);
    }
    
    cout << dfs(1, 0) % mod << "\n";
}

int main() {
    IOS();
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

:::

#### **pD. 樹重心**

:::spoiler Solution (SorahISA)

#pragma GCC optimize("Ofast", "unroll-loops")

#include <cstdio>
#include <vector>
using namespace std;

using lli = long long;

#define Push push_back

#ifdef LOCAL
    inline int nextint() {
        int n; scanf("%d", &n);
        return n;
    }

    inline lli nextlli() {
        lli n; scanf("%lld", &n);
        return n;
    }
#else
    inline char readchar() {
    #define B 1048576
        static char buf[B], *p, *q;
        if(p == q and (q = (p = buf) + fread(buf, 1, B, stdin)) == buf) return EOF;
        return *p++;
    #undef B
    }

    inline int nextint() {
        int x = 0, c = readchar();
        while('0' >  c  or c >  '9') c = readchar();
        while('0' <= c and c <= '9') x = x * 10 + (c ^ '0'), c = readchar();
        return x;
    }

    inline lli nextlli() {
        lli x = 0, c = readchar();
        while('0' >  c  or c >  '9') c = readchar();
        while('0' <= c and c <= '9') x = x * 10 + (c ^ '0'), c = readchar();
        return x;
    }
#endif

const int maxn = 2E5 + 5;
vector<int> adj[maxn], sz(maxn, 1), par(maxn, 0);
int heavy[maxn][2];

void dfs(int now, int lst) {
    for (auto x : adj[now]) {
        if (x == lst) continue;
        dfs(x, now);
        sz[now] += sz[x];
        par[x] = now;
    }
}

void build(int now, int lst) {
    for (auto x : adj[now]) {
        if (x == lst) continue;
        build(x, now);
        
        int pl = heavy[x][0];
        while (pl != now) {
            if ((sz[now] - sz[pl]) * 2 <= sz[now]) {
                bool flag = 1;
                for (auto y : adj[pl]) {
                    if (y == par[pl]) continue;
                    if (sz[y] * 2 > sz[now]) {
                        flag = 0;
                        break;
                    }
                }
                if (flag) {
                    heavy[now][0] = pl;
                    /// check if par[pl] is one of the centroid ///
                    pl = par[pl];
                    
                    if ((sz[now] - sz[pl]) * 2 <= sz[now]) {
                        bool flag2 = 1;
                        for (auto y : adj[pl]) {
                            if (y == par[pl]) continue;
                            if (sz[y] * 2 > sz[now]) {
                                flag2 = 0;
                                break;
                            }
                        }
                        
                        if (flag2) heavy[now][1] = pl;
                    }
                    
                    if (heavy[now][1] and heavy[now][1] < heavy[now][0]) {
                        swap(heavy[now][0], heavy[now][1]);
                    }
                    
                    break;
                }
            }
            pl = par[pl];
        }
    }
    
    if (heavy[now][0] == 0) heavy[now][0] = now;
}

int main() {
    int n, u, v;
    n = nextint();

    for (int i = 0; i < n-1; ++i) {
        u = nextint(); v = nextint();
        adj[u].Push(v);
        adj[v].Push(u);
    }

    dfs(1, -1);

    build(1, -1);
    
    for (int i = 1; i <= n; ++i) {
        printf("%d", heavy[i][0]);
        if (heavy[i][1]) printf(" %d\n", heavy[i][1]);
        else puts("");
    }

    return 0;
}

:::

#### **pE. YP 燈飾店**

:::spoiler Solution (SorahISA)

#include <stdio.h>

char readchar() {
#define B 1048576
    static char buf[B], *p, *q;
    if(p == q && (q = (p = buf) + fread(buf, 1, B, stdin)) == buf) return EOF;
    return *p++;
#undef B
}

int nextint() {
    int x = 0, c = readchar();
    while('0' >  c || c >  '9') c = readchar();
    while('0' <= c && c <= '9') x = x * 10 + (c ^ '0'), c = readchar();
    return x;
}

int v[100005], cal[100005], num[100005], maxNum = 0;

int main() {
    int n = nextint(), k = nextint();

    for (int i = 0; i < k; ++i) {
        v[i] = nextint();
        ++cal[v[i]];
        --num[cal[v[i]] - 1];
        ++num[cal[v[i]]];
        cal[v[i]] > maxNum ? maxNum = cal[v[i]] : 0;
    }

    int lP = 0, ans = k;
    for (int i = k; i < n; ++i) {
        v[i] = nextint();
        ++cal[v[i]];
        --num[cal[v[i]] - 1];
        ++num[cal[v[i]]];
        cal[v[i]] > maxNum ? maxNum = cal[v[i]] : 0;

        while (i - lP + 1 - maxNum > k) {
            --cal[v[lP]];
            --num[cal[v[i]] + 1];
            ++num[cal[v[i]]];

            if (num[cal[v[i]] + 1] == 0) --maxNum;
            ++lP;
        }

        i - lP + 1 > ans ? ans = i - lP + 1 : 0;
    }

    printf("%d\n", ans);
    return 0;
}

:::

:::spoiler Solution (nella17)

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

#define FAST ios::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define Fr(i, s, e) for(auto i = s; i < e; ++i)

signed main() {
    FAST;

    int n, k, ai;
    cin >> n >> k;
    unordered_map<int, vector<int>> va{};
    Fr(i, 0, n) {
        cin >> ai;
        va[ai].emplace_back(i);
    }
    int ans = k+1;
    queue<int> que;
    for(const auto &it: va) {
        while (!que.empty()) que.pop();
        for(const int &x: it.second) {
            while (!que.empty() && x-que.front()-int(que.size()) > k)
                que.pop();
            que.push(x);
            ans = max(ans, x-que.front()+k-(x-que.front()-int(que.size())));
        }
    }
    cout << min(n, ans) << endl;

}

:::

:::spoiler Solution (joylintp)

#include<bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, k, arr[100000], cnt[100001] = {};
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    int r = 0, ans = 0;
    multiset<int> ms;
    ms.insert(0);
    for (int i = 0; i < n; i++)
    {
        while (r < n)
        {
            if (cnt[arr[r]])
                ms.erase(ms.find(cnt[arr[r]]));
            ms.insert(++cnt[arr[r]]);

            if (r - i + 1 - *ms.rbegin() > k)
                break;
            r++;
        }

        ans = max(ans, r - i);
        if (r == n)
            break;

        ms.erase(ms.find(cnt[arr[i]]));
        ms.insert(--cnt[arr[i]]);
        r++;
    }
    cout << ans << '\n';

    return 0;
}

:::

:::spoiler Solution (146)

#include<stdio.h>
#include<algorithm>
int cnt[100001],v[100001],l=0,k,n,ans=0;
inline char readchar() {
    static char buf[1048576], *p, *q;
    if(p == q && (q=(p=buf)+fread(buf,1,1048576,stdin)) == buf) return EOF;
    return *p++;
}
inline int nextint() {
    int x = 0, c = readchar();
    while('0'>c || c>'9') c = readchar();
    while('0'<=c&&c<='9') x = x*10 + (c^'0'), c = readchar();
    return x;
}
int main(){
    n=nextint();
    k=nextint();
    for(int i=1;i<=n;i++){
        v[i]=nextint();
        cnt[v[i]]++;
        while(l!=i&&i-l+1-cnt[v[l]]>k){
            cnt[v[l]]--;
            l++;
        }
        ans=std::max(ans,i-l+1);
    }printf("%d\n",ans);
    return 0;
}

:::

#### **pF. 矩陣乘法**

:::spoiler Solution (nella17)

#pragma GCC optimize("O3,unroll-loops")
#pragma loop_opt(on)
#include <stdio.h>
#include <stdlib.h>

#define Fr(i, s, e) for(auto i = s; i < e; ++i)
#define ll long long
#define ld long double
#define MAX 1200

inline char readchar() {
#define B 1048576
    static char buf[B], *p, *q;
    if(p == q && (q=(p=buf)+fread(buf,1,B,stdin)) == buf) return EOF;
    return *p++;
#undef B
}
inline int nextint() {
    int x = 0, c = readchar();
    while('0'>c || c>'9') c = readchar();
    while('0'<=c&&c<='9') x = x*10 + (c^'0'), c = readchar();
    return x;
}
inline ll nextll() {
    ll x = 0, c = readchar();
    while('0'>c || c>'9') c = readchar();
    while('0'<=c&&c<='9') x = x*10 + (c^'0'), c = readchar();
    return x;
}

#define magic(a, b, m) (a*b - (ll)((ld)a/m*b)*m)

signed main() {

    int n, m, p;
    ll mod, a[MAX][MAX], b[MAX][MAX], r[MAX][MAX], x;
    int T = nextint(); Fr(t, 0, T) {
        n = nextint();
        m = nextint();
        p = nextint();
        mod = nextll();
        Fr(i, 0, n) Fr(j, 0, p) r[i][j] = 0;
        Fr(i, 0, n) Fr(j, 0, m) a[i][j] = nextll()%mod;
        Fr(i, 0, m) Fr(j, 0, p) b[i][j] = nextll()%mod;
        Fr(i, 0, n) Fr(k, 0, m) Fr(j, 0, p) {
            r[i][j] += magic(a[i][k], b[k][j], mod);
            if (r[i][j] >= 8e18) r[i][j] = r[i][j]%mod;
        }
        Fr(i, 0, n) Fr(j, 0, p)
            printf("%lld%c", r[i][j]%mod, " \n"[j==p-1]);
    }

}

:::

#### **pG. 收集堅果**