为什么我的淀粉质 TLE 的如此整齐

x383494 @ 2023-07-13 20:32:45

by x383494 @ 2023-07-13 20:34:08

#include <cstdio>
#include <vector>
#include <iostream>
#include <set>
#define UP(i,s,e) for(auto i=s; i<e; ++i)
namespace m { // }{{{
constexpr int N = 1e4;
int in, im, maxk;
struct Edge{int to, wei; Edge(int t, int w):to(t), wei(w){} };
struct Ask{int k, id; Ask(int k, int id):k(k), id(id){} bool operator<(Ask b)const{ return k < b.k; } }; 
std::multiset<Ask> asks;
int ans[100];
bool deled[N];
int siz[N];
std::vector<Edge> tos[N]; // vector 存边
int find(int x, int fa, int &nowroot, int const &treesiz){ // 找重心
    int xsiz = 1, maxt = 0;
    for(auto i:tos[x]){
        if(deled[i.to] || i.to==fa) continue;
        int isiz = find(i.to, x, nowroot, treesiz);
        xsiz += isiz;
        maxt = std::max(maxt, isiz);
    }
    maxt = std::max(maxt, treesiz - xsiz);
    if(maxt <= treesiz/2) nowroot = x;
    return siz[x] = xsiz;
}
void dfs(int x, int fa, int dis, std::set<int> &ins){ // 求距离
    ins.insert(dis);
    for(auto i:tos[x]){
        if(deled[i.to] || i.to==fa) continue;
        dfs(i.to, x, dis+i.wei, ins);
    }
}
void calc(int x){
    deled[x] = 1;
    static std::set<int> xdis, ndis;
    xdis.clear();
    xdis.insert(0);
    for(auto i:tos[x]){
        if(deled[i.to]) continue;
        dfs(i.to, x, i.wei, ndis);
        for(auto j:ndis){
            for(auto k:asks){
                if(k.k >= j && xdis.find(k.k-j) != xdis.end())
                    ans[k.id]=1;
            }
            if(j > maxk) break;
            xdis.insert(j);
        }
        ndis.clear();
    }
    for(auto i:tos[x]){
        if(deled[i.to]) continue;
        int nroot;
        nroot = find(i.to, x, nroot, siz[i.to]);
        calc(nroot);
    }
}
void work(){
    std::cin >> in >> im;
    UP(i, 1, in) {
        int iu, iv, iw;
        std::cin >> iu >> iv >> iw;
        iu--, iv--;
        tos[iu].emplace_back(iv, iw);
        tos[iv].emplace_back(iu, iw);
    }
    UP(i, 0, im){
        int ik;
        std::cin >> ik;
        maxk = std::max(maxk, ik);
        asks.emplace(ik, i);
    }
    int root = 0;
    find(0, 0, root, in);
    calc(root);
    UP(i, 0, im) std::cout << (ans[i] ? "AYE\n" : "NAY\n");
}
} // {}}}
int main(){m::work(); return 0;}

by x383494 @ 2023-07-13 21:07:37

破案了 这一行假了/kk

 nroot = find(i.to, x, nroot, siz[i.to]);