研究點分治的最好方法是

P3806 【模板】点分治 1

MK14roger @ 2023-12-03 08:59:28

A了這道題!

但是我沒成功

7#9TLE求調

參考的第一篇題解,也看了那篇關於#7的帖子,還是不知道錯哪了

#include <bits/stdc++.h>
using namespace std;

#define int long long

struct edge{
    int b,c;
};

struct node{
    int siz,mx,vis=0;
    vector<edge> e;
} tree[10010]={};

int q[110]={},root=0,tot=0,a[10010]={},intree[10010]={},dis[10010]={},m;
bool ans[110]={};

void dfs(int pos,int fa,int &tot){
    tree[pos].siz=1;
    tree[pos].mx=0;
    for (auto x:tree[pos].e){
        if (tree[x.b].vis || fa==x.b) continue;
        dfs(x.b,pos,tot);
        tree[pos].siz+=tree[x.b].siz;
        tree[pos].mx=max(tree[pos].mx,tree[x.b].siz);
    }
    tree[pos].mx=max(tot-tree[pos].siz,tree[pos].mx);
    if (!root || tree[pos].mx<tree[root].mx) root=pos;
    return;
}

void fnd(int pos,int fa,int dist,int from){
    if (dist>1e7) return;
    a[++tot]=pos;dis[pos]=dist;intree[pos]=from;
    for (auto x:tree[pos].e){
        if (x.b==fa || tree[x.b].vis) continue;
        fnd(x.b,pos,dist+x.c,from);
    }
}

bool cmp(int a,int b){
    return dis[a]<dis[b];
}

void cacu(int pos){
    tot=0;a[++tot]=pos;dis[pos]=0;intree[pos]=pos;
    for (auto x:tree[pos].e){
        if (tree[x.b].vis) continue;
        fnd(x.b,pos,x.c,x.b);
    }
    sort(a+1,a+tot+1,cmp);
    for (int i=1;i<=m;i++){
        int l=1,r=tot;
        if (ans[i]) continue;
        while (l<r){
            if (dis[a[l]]+dis[a[r]]>q[i]) r--;
            else if (dis[a[l]]+dis[a[r]]<q[i]) l++;
            else if (intree[a[l]]==intree[a[r]]){
                if (dis[a[r]]==dis[a[r-1]]) r--;
                else l++;
            }
            else {
                ans[i]=true;
                break;
            }
        }
    }
}

void solve(int pos){
    //cout<<pos<<"\n";
    tree[pos].vis=1;
    cacu(pos);
    for (auto x:tree[pos].e){
        if (tree[x.b].vis) continue;
        root=0;
        dfs(x.b,x.b,tree[x.b].siz);
        solve(root);
    }
}

main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;cin>>n>>m;
    for (int i=1;i<n;i++){
        int a,b,c;cin>>a>>b>>c;
        tree[a].e.push_back({b,c});tree[b].e.push_back({a,c});
    }
    for (int i=1;i<=m;i++){
        cin>>q[i];
        if (q[i]==0) ans[i]=1;
    }
    tree[0].mx=n;
    dfs(1,1,n);
    solve(root);
    for (int i=1;i<=m;i++){
        if (ans[i]) cout<<"AYE"<<"\n";
        else cout<<"NAY"<<"\n";
    }
}

|