Çözüldü TÜBİTAK olimpiyat Can'ın Alt Ağacı sorusunun çözümü

Bu konu çözüldü olarak işaretlenmiştir. Çözülmediğini düşünüyorsanız konuyu rapor edebilirsiniz.

pWrist

Decapat
Katılım
17 Kasım 2020
Mesajlar
98
Çözümler
1
Daha fazla  
Cinsiyet
Erkek
Arkadaşlar hoca PC dersi proje ödevi olarak bu soruyu Python'da çözmemi istedi. Sorunun cevabı var PDF olarak ama ne soruyu ne de cevabını anlamadım. Cevabın olduğu PDF de sorunun kodu da var, sanırım C# dilinde ama emin değilim PDF'i buraya koyacağım. Soruyu anlamada ve kodu yazmamda yardımcı olursanız çok sevinirim.
pdfcanınaltagaciçözüm
 
Son düzenleme:
Çözüm
Kod:
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <map>

#define N 200'005

long long n;
long long k;
long long l;
long long ans = INT_MIN;
long long a[N];
long long u[N];
long long v[N];

std::vector<std::pair<long long, std::pair<long long, long long>>> g[N];
std::vector<long long> pre[N];
std::map <long long, long long> yer[N];

int main() {
    std::cin >> n >> l >> k;

    for (long long i = 1; i <= n; ++i) {
        std::cin >> a[i];
    }

    for (long long i = 1; i < n; ++i) {
        std::cin >> u[i] >> v[i];

        long long vyer = g[u[i]].size();
        long long uyer = g[v[i]].size();

        g[u[i]].push_back(std::make_pair(a[v[i]], std::make_pair(v[i], uyer)));
        g[v[i]].push_back(std::make_pair(a[u[i]], std::make_pair(u[i], vyer)));
    }

    for (long long i = 1; i <= n; ++i) {
        sort(g[i].begin(), g[i].end());
        reverse(g[i].begin(), g[i].end());
    }

    for (size_t i = 1; i <= n; ++i) {
        for (long long j = 0; j < g[i].size(); ++j) {
            yer[g[i][j].second.first][i] = j;
        }
    }

    for (long long i = 1; i <= n; ++i) {
        ans = std::max(ans, a[i]);
    }

    if (k == 1) {
        std::cout << ans << "\n";
        return 0;
    }

    for (long long i = 1; i <= n; ++i) {
        long long mx = 0;
        long long top = 0;

        for (long long j = 0; j < g[i].size(); ++j) {
            top += g[i][j].first;
            mx = std::max(mx, top);
            pre[i].push_back(mx);
        }
    }

    for (long long i = 1; i <= n; ++i) {
        long long top = a[i];
        ans = std::max(ans, top);

        for (long long j = 0; j < std::min(k - 1, (long long)g[i].size()); ++j) {
            top += g[i][j].first;
            ans = std::max(ans, top);
        }

        ans = std::max(ans, top);
    }

    if (l == 3) {
        for (long long i = 1; i < n; ++i) {

            long long top = a[u[i]] + a[v[i]];
            ans = std::max(ans, top);
            long long geldi = 0;

            if ((long long)g[u[i]].size() < (long long)g[v[i]].size()) {
                long long uyer = yer[u[i]][v[i]];

                for (long long j = 0; j < std::min(k - 2, (long long)g[u[i]].size()); ++j) {
                    if (g[u[i]][j].second.first == v[i]) {
                        geldi = 1;
                        continue;
                    }

                    long long bak = k - (j - geldi + 1 + 2) - 1;
                    long long ek = 0;

                    if (bak >= 0) {
                        if (bak >= uyer) {
                            if (a[u[i]] < 0) {
                                if (uyer >= 1) {
                                    ek = pre[v[i]][uyer - 1];
                                }
                            }
                            else {
                                ek = pre[v[i]][std::min(bak + 1, (long long)pre[v[i]].size() - 1)] - a[u[i]];
                            }
                        }
                        else {
                            ek = pre[v[i]][std::min(bak, (long long)pre[v[i]].size() - 1)];
                        }
                    }

                    top += g[u[i]][j].first;
                    ans = std::max(ans, top + ek);
                }
            }
            else {
                long long vyer = yer[v[i]][u[i]];

                for (long long j = 0; j < std::min(k - 2, (long long)g[v[i]].size()); ++j) {
                    if (g[v[i]][j].second.first == u[i]) {
                        geldi = 1;
                        continue;
                    }

                    long long bak = k - (j - geldi + 1 + 2) - 1;
                    long long ek = 0;

                    if (bak >= 0) {
                        if (bak >= vyer) {
                            if (a[v[i]] < 0) {
                                ek = pre[u[i]][vyer - 1];
                            }
                            else {
                                ek = pre[u[i]][std::min(bak + 1, (long long)pre[u[i]].size() - 1)] - a[v[i]];
                            }
                        }
                        else {
                            ek = pre[u[i]][std::min(bak, (long long)pre[u[i]].size() - 1)];
                        }
                    }

                    top += g[v[i]][j].first;
                    ans = std::max(ans, top + ek);
                }
            }
        }
    }

    std::cout << ans << "\n";

    return 0;
}
Kod:
N = 200005

n = 0
k = 0
l = 0
ans = -(2**31)
a = [0 for x in range(N)]
u = [0 for x in range(N)]
v = [0 for x in range(N)]

#g = [[]] * N
g = [[] for x in range(N)]
pre = [[] for x in range(N)]
yer = [{} for x in range(N)]

n, l, k = [int(x) for x in input().split()]
a[1:n + 1] = [int(x) for x in input().split()]

for i in range(1, n):
    u[i], v[i] = [int(x) for x in input().split()]

    vyer = len(g[u[i]])
    uyer = len(g[v[i]])

    g[u[i]].append([a[v[i]], [v[i], uyer]])
    g[v[i]].append([a[u[i]], [u[i], vyer]])

for i in range(1, n + 1):
    #sorted(g[i], reverse=True)
    sorted(g[i])
    g[i].reverse()

for i in range(1, n + 1):
    for j in range(len(g[i])):
        yer[g[i][j][1][0]][i] = j

for i in range(1, n + 1):
    ans = max(ans, a[i])

if k == 1:
    print(ans)
    exit()

for i in range(1, n + 1):
    mx = 0
    top = 0

    for j in range(len(g[i])):
        top += g[i][j][0]
        mx = max(mx, top)
        pre[i].append(mx)

for i in range(1, n + 1):
    top = a[i]
    ans = max(ans, top)

    for j in range(min(k - 1, len(g[i]))):
        top += g[i][j][0]
        ans = max(ans, top)

    ans = max(ans, top)

if l == 3:
    for i in range(1, n):
        top = a[u[i]] + a[v[i]]
        ans = max(ans, top)
        geldi = 0

        if len(g[u[i]]) < len(g[v[i]]):
            uyer = yer[u[i]][v[i]]

            for j in range(min(k - 2, len(g[u[i]]))):
                if g[u[i]][j][1][0] == v[i]:
                    geldi = 1
                    j += 1
                    continue
                    
                bak = k - (j - geldi + 1 + 2) - 1
                ek = 0

                if bak >= 0:
                    if bak >= uyer:
                        if a[u[i]] < 0:
                            if uyer >= 1:
                                ek = pre[v[i]][uyer - 1]
                        else:
                            ek = pre[v[i]][min(
                                bak + 1, len(pre[v[i]]) - 1)] - a[u[i]]
                    else:
                        ek = pre[v[i]][min(bak, len(pre[v[i]]) - 1)]
                
                top += g[u[i]][j][0]
                ans = max(ans, top + ek)
        else:
            vyer = yer[v[i]][u[i]]

            for j in range(min(k - 2, len(g[v[i]]))):
                if g[v[i]][j][1][0] == u[i]:
                    geldi = 1
                    j += 1
                    continue
                
                bak = k - (j - geldi + 1 + 2) - 1
                ek = 0

                if bak >= 0:
                    if bak >= vyer:
                        if a[v[i]] < 0:
                            ek = pre[u[i]][vyer - 1]
                        else:
                            ek = pre[u[i]][min(
                                bak + 1, len(pre[u[i]]) - 1)] - a[v[i]]
                    else:
                        ek = pre[u[i]][min(bak, len(pre[u[i]]) - 1)]

                top += g[v[i]][j][0]
                ans = max(ans, top + ek)

print(ans)
Hepsi böyle rezaletmiş. Kusasım geldi. Akşam zaman ayırıp düzgün C++ halini yazmaya çalışacağım.

Projede tüm istenen sadece bu soruyu Python'a çevirmeniz ise o zamana kadar yaparım.
Herhangi bir hız, bellek kullanımı vb. şart varsa hepsine takılır ama.

Yok hoca herhangi bir şart koymadı. Sadece Python'a çevirmemi istedi. Zaman ayırdığınız için çok teşekkür ederim.
 
Kod:
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <map>

#define N 200'005

long long n;
long long k;
long long l;
long long ans = INT_MIN;
long long a[N];
long long u[N];
long long v[N];

std::vector<std::pair<long long, std::pair<long long, long long>>> g[N];
std::vector<long long> pre[N];
std::map <long long, long long> yer[N];

int main() {
    std::cin >> n >> l >> k;

    for (long long i = 1; i <= n; ++i) {
        std::cin >> a[i];
    }

    for (long long i = 1; i < n; ++i) {
        std::cin >> u[i] >> v[i];

        long long vyer = g[u[i]].size();
        long long uyer = g[v[i]].size();

        g[u[i]].push_back(std::make_pair(a[v[i]], std::make_pair(v[i], uyer)));
        g[v[i]].push_back(std::make_pair(a[u[i]], std::make_pair(u[i], vyer)));
    }

    for (long long i = 1; i <= n; ++i) {
        sort(g[i].begin(), g[i].end());
        reverse(g[i].begin(), g[i].end());
    }

    for (size_t i = 1; i <= n; ++i) {
        for (long long j = 0; j < g[i].size(); ++j) {
            yer[g[i][j].second.first][i] = j;
        }
    }

    for (long long i = 1; i <= n; ++i) {
        ans = std::max(ans, a[i]);
    }

    if (k == 1) {
        std::cout << ans << "\n";
        return 0;
    }

    for (long long i = 1; i <= n; ++i) {
        long long mx = 0;
        long long top = 0;

        for (long long j = 0; j < g[i].size(); ++j) {
            top += g[i][j].first;
            mx = std::max(mx, top);
            pre[i].push_back(mx);
        }
    }

    for (long long i = 1; i <= n; ++i) {
        long long top = a[i];
        ans = std::max(ans, top);

        for (long long j = 0; j < std::min(k - 1, (long long)g[i].size()); ++j) {
            top += g[i][j].first;
            ans = std::max(ans, top);
        }

        ans = std::max(ans, top);
    }

    if (l == 3) {
        for (long long i = 1; i < n; ++i) {

            long long top = a[u[i]] + a[v[i]];
            ans = std::max(ans, top);
            long long geldi = 0;

            if ((long long)g[u[i]].size() < (long long)g[v[i]].size()) {
                long long uyer = yer[u[i]][v[i]];

                for (long long j = 0; j < std::min(k - 2, (long long)g[u[i]].size()); ++j) {
                    if (g[u[i]][j].second.first == v[i]) {
                        geldi = 1;
                        continue;
                    }

                    long long bak = k - (j - geldi + 1 + 2) - 1;
                    long long ek = 0;

                    if (bak >= 0) {
                        if (bak >= uyer) {
                            if (a[u[i]] < 0) {
                                if (uyer >= 1) {
                                    ek = pre[v[i]][uyer - 1];
                                }
                            }
                            else {
                                ek = pre[v[i]][std::min(bak + 1, (long long)pre[v[i]].size() - 1)] - a[u[i]];
                            }
                        }
                        else {
                            ek = pre[v[i]][std::min(bak, (long long)pre[v[i]].size() - 1)];
                        }
                    }

                    top += g[u[i]][j].first;
                    ans = std::max(ans, top + ek);
                }
            }
            else {
                long long vyer = yer[v[i]][u[i]];

                for (long long j = 0; j < std::min(k - 2, (long long)g[v[i]].size()); ++j) {
                    if (g[v[i]][j].second.first == u[i]) {
                        geldi = 1;
                        continue;
                    }

                    long long bak = k - (j - geldi + 1 + 2) - 1;
                    long long ek = 0;

                    if (bak >= 0) {
                        if (bak >= vyer) {
                            if (a[v[i]] < 0) {
                                ek = pre[u[i]][vyer - 1];
                            }
                            else {
                                ek = pre[u[i]][std::min(bak + 1, (long long)pre[u[i]].size() - 1)] - a[v[i]];
                            }
                        }
                        else {
                            ek = pre[u[i]][std::min(bak, (long long)pre[u[i]].size() - 1)];
                        }
                    }

                    top += g[v[i]][j].first;
                    ans = std::max(ans, top + ek);
                }
            }
        }
    }

    std::cout << ans << "\n";

    return 0;
}
Kod:
N = 200005

n = 0
k = 0
l = 0
ans = -(2**31)
a = [0 for x in range(N)]
u = [0 for x in range(N)]
v = [0 for x in range(N)]

#g = [[]] * N
g = [[] for x in range(N)]
pre = [[] for x in range(N)]
yer = [{} for x in range(N)]

n, l, k = [int(x) for x in input().split()]
a[1:n + 1] = [int(x) for x in input().split()]

for i in range(1, n):
    u[i], v[i] = [int(x) for x in input().split()]

    vyer = len(g[u[i]])
    uyer = len(g[v[i]])

    g[u[i]].append([a[v[i]], [v[i], uyer]])
    g[v[i]].append([a[u[i]], [u[i], vyer]])

for i in range(1, n + 1):
    #sorted(g[i], reverse=True)
    sorted(g[i])
    g[i].reverse()

for i in range(1, n + 1):
    for j in range(len(g[i])):
        yer[g[i][j][1][0]][i] = j

for i in range(1, n + 1):
    ans = max(ans, a[i])

if k == 1:
    print(ans)
    exit()

for i in range(1, n + 1):
    mx = 0
    top = 0

    for j in range(len(g[i])):
        top += g[i][j][0]
        mx = max(mx, top)
        pre[i].append(mx)

for i in range(1, n + 1):
    top = a[i]
    ans = max(ans, top)

    for j in range(min(k - 1, len(g[i]))):
        top += g[i][j][0]
        ans = max(ans, top)

    ans = max(ans, top)

if l == 3:
    for i in range(1, n):
        top = a[u[i]] + a[v[i]]
        ans = max(ans, top)
        geldi = 0

        if len(g[u[i]]) < len(g[v[i]]):
            uyer = yer[u[i]][v[i]]

            for j in range(min(k - 2, len(g[u[i]]))):
                if g[u[i]][j][1][0] == v[i]:
                    geldi = 1
                    j += 1
                    continue
                    
                bak = k - (j - geldi + 1 + 2) - 1
                ek = 0

                if bak >= 0:
                    if bak >= uyer:
                        if a[u[i]] < 0:
                            if uyer >= 1:
                                ek = pre[v[i]][uyer - 1]
                        else:
                            ek = pre[v[i]][min(
                                bak + 1, len(pre[v[i]]) - 1)] - a[u[i]]
                    else:
                        ek = pre[v[i]][min(bak, len(pre[v[i]]) - 1)]
                
                top += g[u[i]][j][0]
                ans = max(ans, top + ek)
        else:
            vyer = yer[v[i]][u[i]]

            for j in range(min(k - 2, len(g[v[i]]))):
                if g[v[i]][j][1][0] == u[i]:
                    geldi = 1
                    j += 1
                    continue
                
                bak = k - (j - geldi + 1 + 2) - 1
                ek = 0

                if bak >= 0:
                    if bak >= vyer:
                        if a[v[i]] < 0:
                            ek = pre[u[i]][vyer - 1]
                        else:
                            ek = pre[u[i]][min(
                                bak + 1, len(pre[u[i]]) - 1)] - a[v[i]]
                    else:
                        ek = pre[u[i]][min(bak, len(pre[u[i]]) - 1)]

                top += g[v[i]][j][0]
                ans = max(ans, top + ek)

print(ans)
 
Çözüm
Kod:
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <map>

#define N 200'005

long long n;
long long k;
long long l;
long long ans = INT_MIN;
long long a[N];
long long u[N];
long long v[N];

std::vector<std::pair<long long, std::pair<long long, long long>>> g[N];
std::vector<long long> pre[N];
std::map <long long, long long> yer[N];

int main() {
 std::cin >> n >> l >> k;

 for (long long i = 1; i <= n; ++i) {
 std::cin >> a[i];
 }

 for (long long i = 1; i < n; ++i) {
 std::cin >> u[i] >> v[i];

 long long vyer = g[u[i]].size();
 long long uyer = g[v[i]].size();

 g[u[i]].push_back(std::make_pair(a[v[i]], std::make_pair(v[i], uyer)));
 g[v[i]].push_back(std::make_pair(a[u[i]], std::make_pair(u[i], vyer)));
 }

 for (long long i = 1; i <= n; ++i) {
 sort(g[i].begin(), g[i].end());
 reverse(g[i].begin(), g[i].end());
 }

 for (size_t i = 1; i <= n; ++i) {
 for (long long j = 0; j < g[i].size(); ++j) {
 yer[g[i][j].second.first][i] = j;
 }
 }

 for (long long i = 1; i <= n; ++i) {
 ans = std::max(ans, a[i]);
 }

 if (k == 1) {
 std::cout << ans << "\n";
 return 0;
 }

 for (long long i = 1; i <= n; ++i) {
 long long mx = 0;
 long long top = 0;

 for (long long j = 0; j < g[i].size(); ++j) {
 top += g[i][j].first;
 mx = std::max(mx, top);
 pre[i].push_back(mx);
 }
 }

 for (long long i = 1; i <= n; ++i) {
 long long top = a[i];
 ans = std::max(ans, top);

 for (long long j = 0; j < std::min(k - 1, (long long)g[i].size()); ++j) {
 top += g[i][j].first;
 ans = std::max(ans, top);
 }

 ans = std::max(ans, top);
 }

 if (l == 3) {
 for (long long i = 1; i < n; ++i) {

 long long top = a[u[i]] + a[v[i]];
 ans = std::max(ans, top);
 long long geldi = 0;

 if ((long long)g[u[i]].size() < (long long)g[v[i]].size()) {
 long long uyer = yer[u[i]][v[i]];

 for (long long j = 0; j < std::min(k - 2, (long long)g[u[i]].size()); ++j) {
 if (g[u[i]][j].second.first == v[i]) {
 geldi = 1;
 continue;
 }

 long long bak = k - (j - geldi + 1 + 2) - 1;
 long long ek = 0;

 if (bak >= 0) {
 if (bak >= uyer) {
 if (a[u[i]] < 0) {
 if (uyer >= 1) {
 ek = pre[v[i]][uyer - 1];
 }
 }
 else {
 ek = pre[v[i]][std::min(bak + 1, (long long)pre[v[i]].size() - 1)] - a[u[i]];
 }
 }
 else {
 ek = pre[v[i]][std::min(bak, (long long)pre[v[i]].size() - 1)];
 }
 }

 top += g[u[i]][j].first;
 ans = std::max(ans, top + ek);
 }
 }
 else {
 long long vyer = yer[v[i]][u[i]];

 for (long long j = 0; j < std::min(k - 2, (long long)g[v[i]].size()); ++j) {
 if (g[v[i]][j].second.first == u[i]) {
 geldi = 1;
 continue;
 }

 long long bak = k - (j - geldi + 1 + 2) - 1;
 long long ek = 0;

 if (bak >= 0) {
 if (bak >= vyer) {
 if (a[v[i]] < 0) {
 ek = pre[u[i]][vyer - 1];
 }
 else {
 ek = pre[u[i]][std::min(bak + 1, (long long)pre[u[i]].size() - 1)] - a[v[i]];
 }
 }
 else {
 ek = pre[u[i]][std::min(bak, (long long)pre[u[i]].size() - 1)];
 }
 }

 top += g[v[i]][j].first;
 ans = std::max(ans, top + ek);
 }
 }
 }
 }

 std::cout << ans << "\n";

 return 0;
}
Kod:
N = 200005

n = 0
k = 0
l = 0
ans = -(2**31)
a = [0 for x in range(N)]
u = [0 for x in range(N)]
v = [0 for x in range(N)]

#g = [[]] * N
g = [[] for x in range(N)]
pre = [[] for x in range(N)]
yer = [{} for x in range(N)]

n, l, k = [int(x) for x in input().split()]
a[1:n + 1] = [int(x) for x in input().split()]

for i in range(1, n):
 u[i], v[i] = [int(x) for x in input().split()]

 vyer = len(g[u[i]])
 uyer = len(g[v[i]])

 g[u[i]].append([a[v[i]], [v[i], uyer]])
 g[v[i]].append([a[u[i]], [u[i], vyer]])

for i in range(1, n + 1):
 #sorted(g[i], reverse=True)
 sorted(g[i])
 g[i].reverse()

for i in range(1, n + 1):
 for j in range(len(g[i])):
 yer[g[i][j][1][0]][i] = j

for i in range(1, n + 1):
 ans = max(ans, a[i])

if k == 1:
 print(ans)
 exit()

for i in range(1, n + 1):
 mx = 0
 top = 0

 for j in range(len(g[i])):
 top += g[i][j][0]
 mx = max(mx, top)
 pre[i].append(mx)

for i in range(1, n + 1):
 top = a[i]
 ans = max(ans, top)

 for j in range(min(k - 1, len(g[i]))):
 top += g[i][j][0]
 ans = max(ans, top)

 ans = max(ans, top)

if l == 3:
 for i in range(1, n):
 top = a[u[i]] + a[v[i]]
 ans = max(ans, top)
 geldi = 0

 if len(g[u[i]]) < len(g[v[i]]):
 uyer = yer[u[i]][v[i]]

 for j in range(min(k - 2, len(g[u[i]]))):
 if g[u[i]][j][1][0] == v[i]:
 geldi = 1
 j += 1
 continue

 bak = k - (j - geldi + 1 + 2) - 1
 ek = 0

 if bak >= 0:
 if bak >= uyer:
 if a[u[i]] < 0:
 if uyer >= 1:
 ek = pre[v[i]][uyer - 1]
 else:
 ek = pre[v[i]][min(
 bak + 1, len(pre[v[i]]) - 1)] - a[u[i]]
 else:
 ek = pre[v[i]][min(bak, len(pre[v[i]]) - 1)]

 top += g[u[i]][j][0]
 ans = max(ans, top + ek)
 else:
 vyer = yer[v[i]][u[i]]

 for j in range(min(k - 2, len(g[v[i]]))):
 if g[v[i]][j][1][0] == u[i]:
 geldi = 1
 j += 1
 continue

 bak = k - (j - geldi + 1 + 2) - 1
 ek = 0

 if bak >= 0:
 if bak >= vyer:
 if a[v[i]] < 0:
 ek = pre[u[i]][vyer - 1]
 else:
 ek = pre[u[i]][min(
 bak + 1, len(pre[u[i]]) - 1)] - a[v[i]]
 else:
 ek = pre[u[i]][min(bak, len(pre[u[i]]) - 1)]

 top += g[v[i]][j][0]
 ans = max(ans, top + ek)

print(ans)

Çok teşekkürler vaktinizi ayırdığınız için.
Kod:
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <map>

#define N 200'005.

long long n;
long long k;
long long l;
long long ans = INT_MIN;
long long a[N];
long long u[N];
long long v[N];

std::vector<std::pair<long long, std::pair<long long, long long>>> g[N];
std::vector<long long> pre[N];
std::map <long long, long long> yer[N];

int main() {
 std::cin >> n >> l >> k;

 for (long long i = 1; i <= n; ++i) {
 std::cin >> a[i];
 }

 for (long long i = 1; i < n; ++i) {
 std::cin >> u[i] >> v[i];

 long long vyer = g[u[i]].size();
 long long uyer = g[v[i]].size();

 g[u[i]].push_back(std::make_pair(a[v[i]], std::make_pair(v[i], uyer)));
 g[v[i]].push_back(std::make_pair(a[u[i]], std::make_pair(u[i], vyer)));
 }

 for (long long i = 1; i <= n; ++i) {
 sort(g[i].begin(), g[i].end());
 reverse(g[i].begin(), g[i].end());
 }

 for (size_t i = 1; i <= n; ++i) {
 for (long long j = 0; j < g[i].size(); ++j) {
 yer[g[i][j].second.first][i] = j;
 }
 }

 for (long long i = 1; i <= n; ++i) {
 ans = std::max(ans, a[i]);
 }

 if (k == 1) {
 std::cout << ans << "\n";
 return 0;
 }

 for (long long i = 1; i <= n; ++i) {
 long long mx = 0;
 long long top = 0;

 for (long long j = 0; j < g[i].size(); ++j) {
 top += g[i][j].first;
 mx = std::max(mx, top);
 pre[i].push_back(mx);
 }
 }

 for (long long i = 1; i <= n; ++i) {
 long long top = a[i];
 ans = std::max(ans, top);

 for (long long j = 0; j < std::min(k - 1, (long long)g[i].size()); ++j) {
 top += g[i][j].first;
 ans = std::max(ans, top);
 }

 ans = std::max(ans, top);
 }

 if (l == 3) {
 for (long long i = 1; i < n; ++i) {

 long long top = a[u[i]] + a[v[i]];
 ans = std::max(ans, top);
 long long geldi = 0;

 if ((long long)g[u[i]].size() < (long long)g[v[i]].size()) {
 long long uyer = yer[u[i]][v[i]];

 for (long long j = 0; j < std::min(k - 2, (long long)g[u[i]].size()); ++j) {
 if (g[u[i]][j].second.first == v[i]) {
 geldi = 1;
 continue;
 }

 long long bak = k - (j - geldi + 1 + 2) - 1;
 long long ek = 0;

 if (bak >= 0) {
 if (bak >= uyer) {
 if (a[u[i]] < 0) {
 if (uyer >= 1) {
 ek = pre[v[i]][uyer - 1];
 }
 }
 else {
 ek = pre[v[i]][std::min(bak + 1, (long long)pre[v[i]].size() - 1)] - a[u[i]];
 }
 }
 else {
 ek = pre[v[i]][std::min(bak, (long long)pre[v[i]].size() - 1)];
 }
 }

 top += g[u[i]][j].first;
 ans = std::max(ans, top + ek);
 }
 }
 else {
 long long vyer = yer[v[i]][u[i]];

 for (long long j = 0; j < std::min(k - 2, (long long)g[v[i]].size()); ++j) {
 if (g[v[i]][j].second.first == u[i]) {
 geldi = 1;
 continue;
 }

 long long bak = k - (j - geldi + 1 + 2) - 1;
 long long ek = 0;

 if (bak >= 0) {
 if (bak >= vyer) {
 if (a[v[i]] < 0) {
 ek = pre[u[i]][vyer - 1];
 }
 else {
 ek = pre[u[i]][std::min(bak + 1, (long long)pre[u[i]].size() - 1)] - a[v[i]];
 }
 }
 else {
 ek = pre[u[i]][std::min(bak, (long long)pre[u[i]].size() - 1)];
 }
 }

 top += g[v[i]][j].first;
 ans = std::max(ans, top + ek);
 }
 }
 }
 }

 std::cout << ans << "\n";

 return 0;
}
Kod:
N = 200005.

n = 0
k = 0
l = 0
ans = -(2**31)
a = [0 for x in range(N)]
u = [0 for x in range(N)]
v = [0 for x in range(N)]

#g = [[]] * N
g = [[] for x in range(N)]
pre = [[] for x in range(N)]
yer = [{} for x in range(N)]

n, l, k = [int(x) for x in input().split()]
a[1:n + 1] = [int(x) for x in input().split()]

for i in range(1, n):
 u[i], v[i] = [int(x) for x in input().split()]

 vyer = len(g[u[i]])
 uyer = len(g[v[i]])

 g[u[i]].append([a[v[i]], [v[i], uyer]])
 g[v[i]].append([a[u[i]], [u[i], vyer]])

for i in range(1, n + 1):
 #sorted(g[i], reverse=True)
 sorted(g[i])
 g[i].reverse()

for i in range(1, n + 1):
 for j in range(len(g[i])):
 yer[g[i][j][1][0]][i] = j

for i in range(1, n + 1):
 ans = max(ans, a[i])

if k == 1:
 print(ans)
 exit()

for i in range(1, n + 1):
 mx = 0
 top = 0

 for j in range(len(g[i])):
 top += g[i][j][0]
 mx = max(mx, top)
 pre[i].append(mx)

for i in range(1, n + 1):
 top = a[i]
 ans = max(ans, top)

 for j in range(min(k - 1, len(g[i]))):
 top += g[i][j][0]
 ans = max(ans, top)

 ans = max(ans, top)

if l == 3:
 for i in range(1, n):
 top = a[u[i]] + a[v[i]]
 ans = max(ans, top)
 geldi = 0

 if len(g[u[i]]) < len(g[v[i]]):
 uyer = yer[u[i]][v[i]]

 for j in range(min(k - 2, len(g[u[i]]))):
 if g[u[i]][j][1][0] == v[i]:
 geldi = 1
 j += 1
 continue.

 bak = k - (j - geldi + 1 + 2) - 1
 ek = 0

 if bak >= 0:
 if bak >= uyer:
 if a[u[i]] < 0:
 if uyer >= 1:
 ek = pre[v[i]][uyer - 1]
 else:
 ek = pre[v[i]][min(
 bak + 1, len(pre[v[i]]) - 1)] - a[u[i]]
 else:
 ek = pre[v[i]][min(bak, len(pre[v[i]]) - 1)]

 top += g[u[i]][j][0]
 ans = max(ans, top + ek)
 else:
 vyer = yer[v[i]][u[i]]

 for j in range(min(k - 2, len(g[v[i]]))):
 if g[v[i]][j][1][0] == u[i]:
 geldi = 1
 j += 1
 continue.

 bak = k - (j - geldi + 1 + 2) - 1
 ek = 0

 if bak >= 0:
 if bak >= vyer:
 if a[v[i]] < 0:
 ek = pre[u[i]][vyer - 1]
 else:
 ek = pre[u[i]][min(
 bak + 1, len(pre[u[i]]) - 1)] - a[v[i]]
 else:
 ek = pre[u[i]][min(bak, len(pre[u[i]]) - 1)]

 top += g[v[i]][j][0]
 ans = max(ans, top + ek)

print(ans)

Hocam Jupyter notebook, Visual Studio Code ve Python'da çalıştırdığımda hata verdi sadece Python'da çalıştırdığımda -2147483648 sonucunu verdi. Ama PyCharm da çalışıyor sebebi nedir?
 
Son düzenleme:
Kod:
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <map>

#define N 200'005

long long n;
long long k;
long long l;
long long ans = INT_MIN;
long long a[N];
long long u[N];
long long v[N];

std::vector<std::pair<long long, std::pair<long long, long long>>> g[N];
std::vector<long long> pre[N];
std::map <long long, long long> yer[N];

int main() {
    std::cin >> n >> l >> k;

    for (long long i = 1; i <= n; ++i) {
        std::cin >> a[i];
    }

    for (long long i = 1; i < n; ++i) {
        std::cin >> u[i] >> v[i];

        long long vyer = g[u[i]].size();
        long long uyer = g[v[i]].size();

        g[u[i]].push_back(std::make_pair(a[v[i]], std::make_pair(v[i], uyer)));
        g[v[i]].push_back(std::make_pair(a[u[i]], std::make_pair(u[i], vyer)));
    }

    for (long long i = 1; i <= n; ++i) {
        sort(g[i].begin(), g[i].end());
        reverse(g[i].begin(), g[i].end());
    }

    for (size_t i = 1; i <= n; ++i) {
        for (long long j = 0; j < g[i].size(); ++j) {
            yer[g[i][j].second.first][i] = j;
        }
    }

    for (long long i = 1; i <= n; ++i) {
        ans = std::max(ans, a[i]);
    }

    if (k == 1) {
        std::cout << ans << "\n";
        return 0;
    }

    for (long long i = 1; i <= n; ++i) {
        long long mx = 0;
        long long top = 0;

        for (long long j = 0; j < g[i].size(); ++j) {
            top += g[i][j].first;
            mx = std::max(mx, top);
            pre[i].push_back(mx);
        }
    }

    for (long long i = 1; i <= n; ++i) {
        long long top = a[i];
        ans = std::max(ans, top);

        for (long long j = 0; j < std::min(k - 1, (long long)g[i].size()); ++j) {
            top += g[i][j].first;
            ans = std::max(ans, top);
        }

        ans = std::max(ans, top);
    }

    if (l == 3) {
        for (long long i = 1; i < n; ++i) {

            long long top = a[u[i]] + a[v[i]];
            ans = std::max(ans, top);
            long long geldi = 0;

            if ((long long)g[u[i]].size() < (long long)g[v[i]].size()) {
                long long uyer = yer[u[i]][v[i]];

                for (long long j = 0; j < std::min(k - 2, (long long)g[u[i]].size()); ++j) {
                    if (g[u[i]][j].second.first == v[i]) {
                        geldi = 1;
                        continue;
                    }

                    long long bak = k - (j - geldi + 1 + 2) - 1;
                    long long ek = 0;

                    if (bak >= 0) {
                        if (bak >= uyer) {
                            if (a[u[i]] < 0) {
                                if (uyer >= 1) {
                                    ek = pre[v[i]][uyer - 1];
                                }
                            }
                            else {
                                ek = pre[v[i]][std::min(bak + 1, (long long)pre[v[i]].size() - 1)] - a[u[i]];
                            }
                        }
                        else {
                            ek = pre[v[i]][std::min(bak, (long long)pre[v[i]].size() - 1)];
                        }
                    }

                    top += g[u[i]][j].first;
                    ans = std::max(ans, top + ek);
                }
            }
            else {
                long long vyer = yer[v[i]][u[i]];

                for (long long j = 0; j < std::min(k - 2, (long long)g[v[i]].size()); ++j) {
                    if (g[v[i]][j].second.first == u[i]) {
                        geldi = 1;
                        continue;
                    }

                    long long bak = k - (j - geldi + 1 + 2) - 1;
                    long long ek = 0;

                    if (bak >= 0) {
                        if (bak >= vyer) {
                            if (a[v[i]] < 0) {
                                ek = pre[u[i]][vyer - 1];
                            }
                            else {
                                ek = pre[u[i]][std::min(bak + 1, (long long)pre[u[i]].size() - 1)] - a[v[i]];
                            }
                        }
                        else {
                            ek = pre[u[i]][std::min(bak, (long long)pre[u[i]].size() - 1)];
                        }
                    }

                    top += g[v[i]][j].first;
                    ans = std::max(ans, top + ek);
                }
            }
        }
    }

    std::cout << ans << "\n";

    return 0;
}
Kod:
N = 200005

n = 0
k = 0
l = 0
ans = -(2**31)
a = [0 for x in range(N)]
u = [0 for x in range(N)]
v = [0 for x in range(N)]

#g = [[]] * N
g = [[] for x in range(N)]
pre = [[] for x in range(N)]
yer = [{} for x in range(N)]

n, l, k = [int(x) for x in input().split()]
a[1:n + 1] = [int(x) for x in input().split()]

for i in range(1, n):
    u[i], v[i] = [int(x) for x in input().split()]

    vyer = len(g[u[i]])
    uyer = len(g[v[i]])

    g[u[i]].append([a[v[i]], [v[i], uyer]])
    g[v[i]].append([a[u[i]], [u[i], vyer]])

for i in range(1, n + 1):
    #sorted(g[i], reverse=True)
    sorted(g[i])
    g[i].reverse()

for i in range(1, n + 1):
    for j in range(len(g[i])):
        yer[g[i][j][1][0]][i] = j

for i in range(1, n + 1):
    ans = max(ans, a[i])

if k == 1:
    print(ans)
    exit()

for i in range(1, n + 1):
    mx = 0
    top = 0

    for j in range(len(g[i])):
        top += g[i][j][0]
        mx = max(mx, top)
        pre[i].append(mx)

for i in range(1, n + 1):
    top = a[i]
    ans = max(ans, top)

    for j in range(min(k - 1, len(g[i]))):
        top += g[i][j][0]
        ans = max(ans, top)

    ans = max(ans, top)

if l == 3:
    for i in range(1, n):
        top = a[u[i]] + a[v[i]]
        ans = max(ans, top)
        geldi = 0

        if len(g[u[i]]) < len(g[v[i]]):
            uyer = yer[u[i]][v[i]]

            for j in range(min(k - 2, len(g[u[i]]))):
                if g[u[i]][j][1][0] == v[i]:
                    geldi = 1
                    j += 1
                    continue
                   
                bak = k - (j - geldi + 1 + 2) - 1
                ek = 0

                if bak >= 0:
                    if bak >= uyer:
                        if a[u[i]] < 0:
                            if uyer >= 1:
                                ek = pre[v[i]][uyer - 1]
                        else:
                            ek = pre[v[i]][min(
                                bak + 1, len(pre[v[i]]) - 1)] - a[u[i]]
                    else:
                        ek = pre[v[i]][min(bak, len(pre[v[i]]) - 1)]
               
                top += g[u[i]][j][0]
                ans = max(ans, top + ek)
        else:
            vyer = yer[v[i]][u[i]]

            for j in range(min(k - 2, len(g[v[i]]))):
                if g[v[i]][j][1][0] == u[i]:
                    geldi = 1
                    j += 1
                    continue
               
                bak = k - (j - geldi + 1 + 2) - 1
                ek = 0

                if bak >= 0:
                    if bak >= vyer:
                        if a[v[i]] < 0:
                            ek = pre[u[i]][vyer - 1]
                        else:
                            ek = pre[u[i]][min(
                                bak + 1, len(pre[u[i]]) - 1)] - a[v[i]]
                    else:
                        ek = pre[u[i]][min(bak, len(pre[u[i]]) - 1)]

                top += g[v[i]][j][0]
                ans = max(ans, top + ek)

print(ans)

Ellerinize sağlık hocam, sorunsuz çalışıyor. Müsait bir zamanınızda Python kodu için yorum ekler misiniz? Soru çok ilgimi çekti.
 
Kod:
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <map>

#define N 200'005.

long long n;
long long k;
long long l;
long long ans = INT_MIN;
long long a[N];
long long u[N];
long long v[N];

std::vector<std::pair<long long, std::pair<long long, long long>>> g[N];
std::vector<long long> pre[N];
std::map <long long, long long> yer[N];

int main() {
 std::cin >> n >> l >> k;

 for (long long i = 1; i <= n; ++i) {
 std::cin >> a[i];
 }

 for (long long i = 1; i < n; ++i) {
 std::cin >> u[i] >> v[i];

 long long vyer = g[u[i]].size();
 long long uyer = g[v[i]].size();

 g[u[i]].push_back(std::make_pair(a[v[i]], std::make_pair(v[i], uyer)));
 g[v[i]].push_back(std::make_pair(a[u[i]], std::make_pair(u[i], vyer)));
 }

 for (long long i = 1; i <= n; ++i) {
 sort(g[i].begin(), g[i].end());
 reverse(g[i].begin(), g[i].end());
 }

 for (size_t i = 1; i <= n; ++i) {
 for (long long j = 0; j < g[i].size(); ++j) {
 yer[g[i][j].second.first][i] = j;
 }
 }

 for (long long i = 1; i <= n; ++i) {
 ans = std::max(ans, a[i]);
 }

 if (k == 1) {
 std::cout << ans << "\n";
 return 0;
 }

 for (long long i = 1; i <= n; ++i) {
 long long mx = 0;
 long long top = 0;

 for (long long j = 0; j < g[i].size(); ++j) {
 top += g[i][j].first;
 mx = std::max(mx, top);
 pre[i].push_back(mx);
 }
 }

 for (long long i = 1; i <= n; ++i) {
 long long top = a[i];
 ans = std::max(ans, top);

 for (long long j = 0; j < std::min(k - 1, (long long)g[i].size()); ++j) {
 top += g[i][j].first;
 ans = std::max(ans, top);
 }

 ans = std::max(ans, top);
 }

 if (l == 3) {
 for (long long i = 1; i < n; ++i) {

 long long top = a[u[i]] + a[v[i]];
 ans = std::max(ans, top);
 long long geldi = 0;

 if ((long long)g[u[i]].size() < (long long)g[v[i]].size()) {
 long long uyer = yer[u[i]][v[i]];

 for (long long j = 0; j < std::min(k - 2, (long long)g[u[i]].size()); ++j) {
 if (g[u[i]][j].second.first == v[i]) {
 geldi = 1;
 continue;
 }

 long long bak = k - (j - geldi + 1 + 2) - 1;
 long long ek = 0;

 if (bak >= 0) {
 if (bak >= uyer) {
 if (a[u[i]] < 0) {
 if (uyer >= 1) {
 ek = pre[v[i]][uyer - 1];
 }
 }
 else {
 ek = pre[v[i]][std::min(bak + 1, (long long)pre[v[i]].size() - 1)] - a[u[i]];
 }
 }
 else {
 ek = pre[v[i]][std::min(bak, (long long)pre[v[i]].size() - 1)];
 }
 }

 top += g[u[i]][j].first;
 ans = std::max(ans, top + ek);
 }
 }
 else {
 long long vyer = yer[v[i]][u[i]];

 for (long long j = 0; j < std::min(k - 2, (long long)g[v[i]].size()); ++j) {
 if (g[v[i]][j].second.first == u[i]) {
 geldi = 1;
 continue;
 }

 long long bak = k - (j - geldi + 1 + 2) - 1;
 long long ek = 0;

 if (bak >= 0) {
 if (bak >= vyer) {
 if (a[v[i]] < 0) {
 ek = pre[u[i]][vyer - 1];
 }
 else {
 ek = pre[u[i]][std::min(bak + 1, (long long)pre[u[i]].size() - 1)] - a[v[i]];
 }
 }
 else {
 ek = pre[u[i]][std::min(bak, (long long)pre[u[i]].size() - 1)];
 }
 }

 top += g[v[i]][j].first;
 ans = std::max(ans, top + ek);
 }
 }
 }
 }

 std::cout << ans << "\n";

 return 0;
}
Kod:
N = 200005.

n = 0
k = 0
l = 0
ans = -(2**31)
a = [0 for x in range(N)]
u = [0 for x in range(N)]
v = [0 for x in range(N)]

#g = [[]] * N
g = [[] for x in range(N)]
pre = [[] for x in range(N)]
yer = [{} for x in range(N)]

n, l, k = [int(x) for x in input().split()]
a[1:n + 1] = [int(x) for x in input().split()]

for i in range(1, n):
 u[i], v[i] = [int(x) for x in input().split()]

 vyer = len(g[u[i]])
 uyer = len(g[v[i]])

 g[u[i]].append([a[v[i]], [v[i], uyer]])
 g[v[i]].append([a[u[i]], [u[i], vyer]])

for i in range(1, n + 1):
 #sorted(g[i], reverse=True)
 sorted(g[i])
 g[i].reverse()

for i in range(1, n + 1):
 for j in range(len(g[i])):
 yer[g[i][j][1][0]][i] = j

for i in range(1, n + 1):
 ans = max(ans, a[i])

if k == 1:
 print(ans)
 exit()

for i in range(1, n + 1):
 mx = 0
 top = 0

 for j in range(len(g[i])):
 top += g[i][j][0]
 mx = max(mx, top)
 pre[i].append(mx)

for i in range(1, n + 1):
 top = a[i]
 ans = max(ans, top)

 for j in range(min(k - 1, len(g[i]))):
 top += g[i][j][0]
 ans = max(ans, top)

 ans = max(ans, top)

if l == 3:
 for i in range(1, n):
 top = a[u[i]] + a[v[i]]
 ans = max(ans, top)
 geldi = 0

 if len(g[u[i]]) < len(g[v[i]]):
 uyer = yer[u[i]][v[i]]

 for j in range(min(k - 2, len(g[u[i]]))):
 if g[u[i]][j][1][0] == v[i]:
 geldi = 1
 j += 1
 continue.

 bak = k - (j - geldi + 1 + 2) - 1
 ek = 0

 if bak >= 0:
 if bak >= uyer:
 if a[u[i]] < 0:
 if uyer >= 1:
 ek = pre[v[i]][uyer - 1]
 else:
 ek = pre[v[i]][min(
 bak + 1, len(pre[v[i]]) - 1)] - a[u[i]]
 else:
 ek = pre[v[i]][min(bak, len(pre[v[i]]) - 1)]

 top += g[u[i]][j][0]
 ans = max(ans, top + ek)
 else:
 vyer = yer[v[i]][u[i]]

 for j in range(min(k - 2, len(g[v[i]]))):
 if g[v[i]][j][1][0] == u[i]:
 geldi = 1
 j += 1
 continue.

 bak = k - (j - geldi + 1 + 2) - 1
 ek = 0

 if bak >= 0:
 if bak >= vyer:
 if a[v[i]] < 0:
 ek = pre[u[i]][vyer - 1]
 else:
 ek = pre[u[i]][min(
 bak + 1, len(pre[u[i]]) - 1)] - a[v[i]]
 else:
 ek = pre[u[i]][min(bak, len(pre[u[i]]) - 1)]

 top += g[v[i]][j][0]
 ans = max(ans, top + ek)

print(ans)

Ekte verdiğim hatayı Jupyter notebook veriyor.
 

Dosya Ekleri

  • hata.png
    hata.png
    4,7 KB · Görüntüleme: 45
Ekte verdiğim hatayı Jupyter notebook veriyor.
Verdiğim kodu kullanırsanız hata vereceğini sanmıyorum. Ben C++ bilmediğiniz için ödevinizi yapamadığınızı sanıyordum ama görüyorum ki zahmet edip koda bakmaya, yapıştırdığınızda oluşan karakter çakışmasını fark edecek kadar özen göstermeye bile tenezzül etmemişsiniz.
PyCharm'da düzgün çalışmasının sebebi PyCharm'ın düzgün olmasıdır. VS Code'da düzgün çalışmaması asıl ilginç olan. Kodu onda yazdım. Siz muhtemelen birinden alıp birine verdiniz, sonra oradan alıp diğerine vermeye çalıştınız.
Ellerinize sağlık hocam, sorunsuz çalışıyor. Müsait bir zamanınızda Python kodu için yorum ekler misiniz? Soru çok ilgimi çekti.
Yorum ekleyecek bir şey yok. Kodu ben yazmadım. Konuda kaynak bulabilirsiniz. Orijinali iğrenç olan bir C++ kodunu (çok da vakit harcamamak ve gerçekten düzeltmek için kodu da anlamak gerektiği için) okunacak seviyeye getirdim. Sonra da onu bildiğim kadarıyla Python'a çevirdim.
Python kodunda birkaç yorum şeklinde kod satırı var. Bunlar üstündeki/altındaki aynı işlevi yapan satırların alternatifi olması gerekirken farklı sonuç veren halleri Python'a hakim olsam neden böyle olduğunu bilebilirdim ama bilmiyorum.
 
Son düzenleme:
Verdiğim kodu kullanırsanız hata vereceğini sanmıyorum. Ben C++ bilmediğiniz için ödevinizi yapamadığınızı sanıyordum ama görüyorum ki zahmet edip koda bakmaya, yapıştırdığınızda oluşan karakter çakışmasını fark edecek kadar özen göstermeye bile tenezzül etmemişsiniz.
PyCharm'da düzgün çalışmasının sebebi PyCharm'ın düzgün olmasıdır. VS Code'da düzgün çalışmaması asıl ilginç olan. Kodu onda yazdım. Siz muhtemelen birinden alıp birine verdiniz, sonra oradan alıp diğerine vermeye çalıştınız.

Yorum ekleyecek bir şey yok. Kodu ben yazmadım. Konuda kaynak bulabilirsiniz. Orijinali iğrenç olan bir C++ kodunu (çok da vakit harcamamak ve gerçekten düzeltmek için kodu da anlamak gerektiği için) okunacak seviyeye getirdim. Sonra da onu bildiğim kadarıyla Python'a çevirdim.
Python kodunda birkaç yorum şeklinde kod satırı var. Bunlar üstündeki/altındaki aynı işlevi yapan satırların alternatifi olması gerekirken farklı sonuç veren halleri Python'a hakim olsam neden böyle olduğunu bilebilirdim ama bilmiyorum.

Aslında ne deseniz haklısınız şu an yaptığım şey kolaya kaçmak. Kodlama öğrenmek istiyorum ama çok karmaşık geliyor. Proje ödevini de aldığım zamandan beri hiçbir şey yapamayınca konu açmak istedim çünkü biliyorum ki tek başıma bu projeyle ilgili hiçbir halt yapamazdım... Dediğiniz gibi karakter çakışması olmuş onları düzeltince diğer programlarda da sorunsuz çalıştı teşekkür ederim.
 

Geri
Yukarı