89822024-02-09 21:55:28Vkrisztian01Testvérvárosokcpp17Runtime error 0/100268ms524692 KiB
#include <iostream>
#include <vector>
#include <deque>
using namespace std;



int n,k,a,b;
vector<vector<int>> g;

int64_t   osszefesul(deque<int>& a, deque<int>& b)
 {
    if (a.size() < b.size()) swap(a, b);
    int egyikmeret = a.size();
      int masikmeret = b.size();

    int64_t ki = 0;
    for (int i = max(0, (k-    masikmeret) + 1); i < min(k +1,egyikmeret); i++)
{
        ki += a[i] * b[k-i];
    }
    for (int i = 0; i < masikmeret; i++) a[i] += b[i];
    return ki;
}

pair<int64_t, deque<int>> f(int csucs,int szulo)
{
    pair<int64_t, deque<int>> seged;
    seged.first=0;
    seged.second.push_back(1);
    for (auto to : g[csucs])
        {
        if (to == szulo) continue;
        pair<int64_t,deque<int> > gyerkoc= f(to, csucs);
        gyerkoc.second.push_front(0);
        seged.first += gyerkoc.first + osszefesul(seged.second, gyerkoc.second);
        if(seged.second.size()>k)
        {
            seged.second[0]+=seged.second[k];
            seged.second.pop_back();
        }
        }
    return seged;
}

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

    cout<<f(1,0).first;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1956 KiB
2Runtime error218ms524692 KiB
subtask20/15
3Runtime error4ms2804 KiB
4Wrong answer3ms2908 KiB
5Runtime error4ms3520 KiB
6Runtime error3ms3116 KiB
7Runtime error3ms3136 KiB
8Runtime error263ms523832 KiB
9Runtime error194ms523784 KiB
subtask30/15
10Runtime error219ms523744 KiB
11Wrong answer4ms3600 KiB
12Runtime error222ms523484 KiB
13Wrong answer17ms8516 KiB
14Runtime error226ms523192 KiB
subtask40/20
15Runtime error4ms4044 KiB
16Runtime error204ms523188 KiB
17Runtime error189ms523080 KiB
18Runtime error197ms523040 KiB
19Runtime error200ms523068 KiB
20Runtime error202ms523064 KiB
21Runtime error202ms523064 KiB
22Runtime error204ms523060 KiB
subtask50/50
23Runtime error222ms523052 KiB
24Runtime error203ms523028 KiB
25Runtime error216ms523016 KiB
26Runtime error202ms523020 KiB
27Runtime error211ms523036 KiB
28Runtime error224ms523028 KiB
29Runtime error250ms523036 KiB
30Runtime error225ms523032 KiB
31Runtime error268ms522944 KiB