求调点分治，调了一天调崩溃了QAQ

HaloisAWA @ 2024-11-10 23:41:43

#include<bits/stdc++.h>
using namespace std;
struct node{
    int v,w;
    node(int vv,int ww) {
        v = vv;
        w = ww;
        return;
    }
};
int n,m,ut,vt,wt,k;
long long dp[40010],dis[40010],maxn,ans;
vector<node> g[40010];
vector<pair<long long,int> > d;
bool vis[40010];
int center,l,r,cnt;
void dfs1(int u,int fa) {
    long long tmp = 0;
    dp[u] = 1;
    for (int i = 0;i < g[u].size();i ++) {
        int v = g[u][i].v,w = g[u][i].w;
        if (v != fa && (!vis[v])) {
            dfs1(v,u);
            dp[u] += dp[v];
            tmp = max(tmp,dp[v]);
        }
    }
    tmp = max(tmp,cnt - dp[u]);//////
    if (tmp < maxn) center = u;
    return;
}
void dfs2(int u,int fa,int colr) {
    d.push_back(make_pair(dis[u],colr));//放在这里是为了保证根节点进入vector 
    for (int i = 0;i < g[u].size();i ++) {
        int v = g[u][i].v,w = g[u][i].w;
        if (v != fa && (!vis[v])) {
            dis[v] = dis[u] + w;//这句话放在dfs2前面 
            dfs2(v,u,colr);
        }
    }
    return;
}
void calc(int u,int val) {
    dis[u] = 0;//
    d.clear();//

    d.push_back(make_pair(dis[u],u));
    for (int i = 0;i < g[u].size();i ++) {
        int v = g[u][i].v,w = g[u][i].w;
        if (!vis[v]) {
            dis[v] = dis[u] + w;
            dfs2(v,u,v);
        }
    }

    sort(d.begin(),d.end());//
    l = 0;
    r = d.size() - 1;
    while (l < r) {
        if (d[l].first + d[r].first == val) {
            printf("AYE\n");
            exit(0);
        } else if (d[l].first + d[r].first < val) ++ l;
        else -- r;
    }
    return;
}
void solve(int u) {
    vis[u] = true;
    calc(u,k);
    for (int i = 0;i < g[u].size();i ++) {
        int v = g[u][i].v,w = g[u][i].w;
        if (!vis[v]) {
            cnt = dp[v];//
            maxn = 0x7fffffff;//
            dfs1(v,0);
            solve(center);
        }
    }
    return;
}
int main() {
    scanf("%d%d",&n,&m);
    for (int i = 1;i < n;i ++) {
        scanf("%d%d%d",&ut,&vt,&wt);
        g[ut].push_back(node(vt,wt));
        g[vt].push_back(node(ut,wt));
    }
    for (int kkk = 1;kkk <= m;kkk ++) {
        scanf("%d",&k);
        maxn = 0x7fffffff;
        cnt = n;
        dfs1(1,0);//找重心 
        //dis[center] = 0;
        solve(center);
        printf("NAY\n");
    }
    return 0;
}

by Melo_DDD @ 2024-11-11 00:43:41

@HaloisAWA

if (tmp < maxn) center = u;

哥们你不觉得你应该更新一下 maxn 吗

by HaloisAWA @ 2024-11-11 09:02:39

@Melo_DDD 卧槽重心就写错了

by HaloisAWA @ 2024-11-11 09:03:40

@Melo_DDD 刚才AC了,不知道为什么改成离线处理就AC了

#include<bits/stdc++.h>
using namespace std;
struct node{
    int v,w;
    node(int vv,int ww) {
        v = vv;
        w = ww;
        return;
    }
};
int n,m,ut,vt,wt,k;
long long dp[40010],dis[40010],maxn;
vector<node> g[40010];
vector<pair<long long,int> > d;
vector<int> query;
bool ans[40010];
bool vis[40010],flag;
int center,l,r,cnt;
void dfs1(int u,int fa) {
    long long tmp = 0;
    dp[u] = 1;
    for (int i = 0;i < g[u].size();i ++) {
        int v = g[u][i].v,w = g[u][i].w;
        if (v != fa && (!vis[v])) {
            dfs1(v,u);
            dp[u] += dp[v];
            tmp = max(tmp,dp[v]);
        }
    }
    tmp = max(tmp,cnt - dp[u]);//////
    if (tmp < maxn) {
        center = u;
        maxn = tmp;
    }
    return;
}
void dfs2(int u,int fa,int colr) {
    d.push_back(make_pair(dis[u],colr));//放在这里是为了保证根节点进入vector 
    for (int i = 0;i < g[u].size();i ++) {
        int v = g[u][i].v,w = g[u][i].w;
        if (v != fa && (!vis[v])) {
            dis[v] = dis[u] + w;//这句话放在dfs2前面 
            dfs2(v,u,colr);
        }
    }
    return;
}
void calc(int u) {
    dis[u] = 0;//
    d.clear();//

    d.push_back(make_pair(dis[u],u));
    for (int i = 0;i < g[u].size();i ++) {
        int v = g[u][i].v,w = g[u][i].w;
        if (!vis[v]) {
            dis[v] = dis[u] + w;
            dfs2(v,u,v);
        }
    }

    sort(d.begin(),d.end());//
    for (int i = 1;i <= m;i ++) {
        if (ans[i]) {
            //printf("-----\n");
            continue;
        }
        l = 0;
        r = d.size() - 1;
        int val = query[i - 1];
        while (l < r) {
            if (d[l].first + d[r].first == val) {
                if (d[l].second != d[r].second) { 
                    ans[i] = true;
                    break;
                } else {
                    ++ l;
                }
            } else if (d[l].first + d[r].first < val) ++ l;
            else -- r;
        }
    }
    return;
}
void solve(int u) {
    vis[u] = true;
    calc(u);
    for (int i = 0;i < g[u].size();i ++) {
        int v = g[u][i].v,w = g[u][i].w;
        if (!vis[v]) {
            cnt = dp[v];//
            maxn = 0x7fffffff;//
            dfs1(v,0);
            solve(center);
        }
    }
    return;
}
int main() {
    scanf("%d%d",&n,&m);
    for (int i = 1;i < n;i ++) {
        scanf("%d%d%d",&ut,&vt,&wt);
        g[ut].push_back(node(vt,wt));
        g[vt].push_back(node(ut,wt));
    }
    for (int kkk = 1;kkk <= m;kkk ++) {
        scanf("%d",&k);
        query.push_back(k);
    }
    maxn = 0x7fffffff;
    cnt = n;
    flag = false;
    dfs1(1,0);//找重心 
    //dis[center] = 0;
    solve(center);
    for (int i = 1;i <= m;i ++)
        if (ans[i]) printf("AYE\n");
        else printf("NAY\n");
    return 0;
}

by HaloisAWA @ 2024-11-11 09:04:27

@Melo_DDD 这个是没离线处理的代码

#include<bits/stdc++.h>
using namespace std;
struct node{
    int v,w;
    node(int vv,int ww) {
        v = vv;
        w = ww;
        return;
    }
};
int n,m,ut,vt,wt,k;
long long dp[40010],dis[40010],maxn,ans;
vector<node> g[40010];
vector<pair<long long,int> > d;
vector<int> query;
bool vis[40010],flag;
int center,l,r,cnt;
void dfs1(int u,int fa) {
    long long tmp = 0;
    dp[u] = 1;
    for (int i = 0;i < g[u].size();i ++) {
        int v = g[u][i].v,w = g[u][i].w;
        if (v != fa && (!vis[v])) {
            dfs1(v,u);
            dp[u] += dp[v];
            tmp = max(tmp,dp[v]);
        }
    }
    tmp = max(tmp,cnt - dp[u]);//////
    if (tmp < maxn) {
        center = u;
        maxn = tmp;
    }
    return;
}
void dfs2(int u,int fa,int colr) {
    d.push_back(make_pair(dis[u],colr));//放在这里是为了保证根节点进入vector 
    for (int i = 0;i < g[u].size();i ++) {
        int v = g[u][i].v,w = g[u][i].w;
        if (v != fa && (!vis[v])) {
            dis[v] = dis[u] + w;//这句话放在dfs2前面 
            dfs2(v,u,colr);
        }
    }
    return;
}
void calc(int u,int val) {
    dis[u] = 0;//
    d.clear();//

    d.push_back(make_pair(dis[u],u));
    for (int i = 0;i < g[u].size();i ++) {
        int v = g[u][i].v,w = g[u][i].w;
        if (!vis[v]) {
            dis[v] = dis[u] + w;
            dfs2(v,u,v);
        }
    }

    sort(d.begin(),d.end());//
    l = 0;
    r = d.size() - 1;
    while (l < r) {
        if (d[l].first + d[r].first == val) {
            if (d[l].second != d[r].second) { 
                printf("AYE\n");
                return;
            } else {
                ++ l;
            }
        } else if (d[l].first + d[r].first < val) ++ l;
        else -- r;
    }
    return;
}
void solve(int u) {
    vis[u] = true;
    calc(u,k);
    for (int i = 0;i < g[u].size();i ++) {
        int v = g[u][i].v,w = g[u][i].w;
        if (!vis[v]) {
            cnt = dp[v];//
            maxn = 0x7fffffff;//
            dfs1(v,0);
            solve(center);
        }
    }
    return;
}
int main() {
    scanf("%d%d",&n,&m);
    for (int i = 1;i < n;i ++) {
        scanf("%d%d%d",&ut,&vt,&wt);
        g[ut].push_back(node(vt,wt));
        g[vt].push_back(node(ut,wt));
    }
    for (int kkk = 1;kkk <= m;kkk ++) {
        scanf("%d",&k);
    maxn = 0x7fffffff;
    cnt = n;
    flag = false;
    dfs1(1,0);//找重心 
    //dis[center] = 0;
    solve(center);
    if (!flag) printf("NAY\n");
        //query.push_back(k);
    }

    return 0;
}

by HaloisAWA @ 2024-11-11 09:23:35

@Melo_DDD 主要是离线处理可以在calc里面判断ans[i]有没有处理过,毕竟一个只能处理一次