点分治TLE on #7#9求调

yyrwlj @ 2024-06-10 18:51:02

#include <iostream>
#include <vector>
using namespace std;
const int N = 10005, K = 10000005, inf = 1e9;
struct Edge{
    int e, to, nxt;
}g[N << 1];
int h[N], idx;
bool ans[N], st[N];
int vis[K], Time;
int siz[N], mx[N], dist[N], sum, root;
int dis[N], tot;
int q[N], n, m;
void add(int a,int b,int c)
{
    g[++idx] = {c, b, h[a]}, h[a] = idx;
}
void dfs_size(int u,int fa)
{
    siz[u] = 1;
    mx[u] = 0;
    for (int i = h[u]; i; i = g[i].nxt)
    {
        int j = g[i].to;
        if (j == fa || st[j])
            continue;
        dfs_size(j, u);
        mx[u] = max(mx[u], siz[j]);
        siz[u] += siz[j];
    }
    mx[u] = max(mx[u], sum - siz[u]);
    if (mx[u] < mx[root])
        root = u;
}
void dfs_dist(int u,int fa)
{
    dis[++ tot] = dist[u];
    for (int i = h[u]; i; i = g[i].nxt)
    {
        int j = g[i].to;
        if (j == fa || st[j])
            continue;
        dist[j] = dist[u] + g[i].e;
        if (dist[j] <= 10000000)
            dfs_dist(j, u);
    }
}
void dfs(int u,int fa)
{
    vis[0] = ++ Time;
    st[u] = true;
    for (int i = h[u]; i; i = g[i].nxt)
    {
        int j = g[i].to;
        if (j == fa || st[j])
            continue;
        tot = 0;
        dist[j] = g[i].e;
        dfs_dist(j, u);
        for (int d=1;d<=tot;d++)
            for (int k=1;k<=m;k++)
                if (dis[d] <= q[k])
                    ans[k] |= vis[q[k] - dis[d]] == Time;
        for (int d=1;d<=tot;d++)
            vis[dis[d]] = Time;
    }
    for (int i = h[u]; i; i = g[i].nxt)
    {
        int j = g[i].to;
        if (j == fa || st[j])
            continue;
        sum = siz[j];
        root = 0;
        mx[root] = inf;
        dfs_size(j, u);
        dfs_size(root, root);
        dfs(j, u);
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i=1;i<n;i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    }
    for (int i=1;i<=m;i++)
        scanf("%d", &q[i]);
    mx[root] = inf;
    sum = n;
    dfs_size(1, 1);
    dfs_size(root, root);
    dfs(root, root);
    for (int i=1;i<=m;i++)
        if (ans[i])
            puts("AYE");
        else
            puts("NAY");
    return 0;
}

by HEROBRINEH @ 2024-06-10 19:19:48

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 9,M = 109,K = 1e7 + 9;
int n,m;
struct edge{
    int to,cost,nex;
} e[N << 1];
int head[N],ecnt;
void addedge(int u,int v,int w){
    ecnt++;
    e[ecnt] = (edge){v,w,head[u]};
    head[u] = ecnt;
}
int dp[N],siz[N],dis[N];
int rec[N],rec_top;
int tmp[K],tmp_top;
bool vis[N];
int query[M];
bool exist[K],ans[M];
int tot,Center;
void get_center(int u,int fa){
    dp[u] = 0;siz[u] = 1;
    for(int i = head[u];i;i = e[i].nex){
        int v = e[i].to,w = e[i].cost;
        if(vis[v] || v == fa)
            continue;
        get_center(v,u);
        siz[u] += siz[v];
        dp[u] = max(dp[u],siz[v]);
    }
    dp[u]=max(dp[u],tot - siz[u]);
    if(dp[u] < dp[Center]) 
        Center = u;
}
void get_dis(int u,int fa){
    rec[++rec_top] = dis[u];
    for(int i = head[u];i;i = e[i].nex){
        int v = e[i].to,w = e[i].cost;
        if(vis[v] || v == fa)
            continue;
        dis[v] = dis[u] + w;
        get_dis(v,u);
    }
}
void merge(int u){
    tmp_top = 0;
    for(int i = head[u];i;i = e[i].nex){
        int v = e[i].to,w = e[i].cost;
        if(vis[v])
            continue;
        rec_top = 0;dis[v] = w;
        get_dis(v,u);
        for(int j = 1;j <= rec_top;j++)
            for(int k = 1;k <= m;k++)
                if(query[k] >= rec[j])
                    ans[k] |= exist[query[k] - rec[j]];
        for(int j = 1;j <= rec_top;j++){
            tmp[++tmp_top] = rec[j];
            exist[rec[j]] = true;
        }
    }
    for(int i = 1;i <= tmp_top;i++)
        exist[tmp[i]] = false;
}
void solve(int u){
    vis[u] = true;
    merge(u);
    for(int i = head[u];i;i = e[i].nex){
        int v = e[i].to,w = e[i].cost;
        if(vis[v])
            continue;
        dp[0] = n;Center = 0;tot = siz[v];
        get_center(v,u);
        solve(Center);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i < n;i++){
        int u,v,w;
        cin >> u >> v >> w;
        addedge(u,v,w);
        addedge(v,u,w);
    }
    for(int i = 1;i <= m;i++)
        cin >> query[i];
    dp[0] = tot = n;
    get_center(1,0);
    exist[0] = true;
    solve(Center);
    for(int i = 1;i <= m;i++)
        cout << (ans[i] ? "AYE" : "NAY") << '\n';
    return 0;
}

by run_away @ 2024-06-10 19:28:44

@yyrwlj 把dfs(j,u)改为dfs(root,u)

by run_away @ 2024-06-10 19:29:37

@yyrwlj 如果用j进行下一次搜索，那就是 n^2的

by yyrwlj @ 2024-06-10 20:05:56

@run_away stO Orz,wssb