点分治60pts求助，#7和#9 T 了

UperFicial @ 2022-01-13 22:05:06

by UperFicial @ 2022-01-13 22:05:14

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<cctype>
#include<stack>
#include<map>
#include<climits>
#include<set>
#include<iostream>
#define rint() read<int>()
#define rll() read<ll>()
using namespace std;
typedef long long ll;
inline int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+(ch-'0'),ch=getchar();
    return s*w;
}
const int INF=1e9;
const ll LLINF=1e18;
template<typename T>
inline T Min(T x,T y){return x<y?x:y;}
template<typename T>
inline T Max(T x,T y){return x>y?x:y;}
template<typename T>
inline void Swap(T&x,T&y){x^=y;y^=x;x^=y;}
const int MAXN(10010);
const int MAXD(102210101);
int n,m;
struct E{int to,nxt,cost;};
E edge[MAXN<<1];
int head[MAXN],tot;
int S,siz[MAXN],maxx[MAXN],root;
int ans;
bool vis[MAXN];
int dis[MAXN],st[MAXN],top;
int mp[MAXD];
inline void add_edge(int u,int v,int w)
{
    edge[++tot].nxt=head[u];
    head[u]=tot;
    edge[tot].to=v;
    edge[tot].cost=w;
    return;
}
inline void Find_Center(int u,int fa)
{
    siz[u]=1,maxx[u]=0;
    for(register int i=head[u];i;i=edge[i].nxt)
    {
        E e=edge[i];
        if(e.to==fa||vis[e.to]) continue;
        Find_Center(e.to,u);
        siz[u]+=siz[e.to];
        maxx[u]=Max(maxx[u],siz[e.to]);
    }
    maxx[u]=Max(maxx[u],S-siz[u]);
    if(maxx[u]<maxx[root]) root=u;
    return; 
}
inline void get_dis(int u,int fa,int len)
{
    st[++top]=dis[u];
    for(register int i=head[u];i;i=edge[i].nxt)
    {
        E e=edge[i];
        if(e.to==fa||vis[e.to]) continue;
        dis[e.to]=len+e.cost;
        get_dis(e.to,u,dis[e.to]);
    }
    return;
}
inline void solve(int u,int len,int w)
{
    top=0;
    dis[u]=len;
    get_dis(u,0,len);
    for(register int i=1;i<=top;i++)
        for(register int j=1;j<=top;j++)
            if(i!=j) mp[st[i]+st[j]]+=w;
    return;
}
inline void dfs(int u)
{
    solve(u,0,1);
    vis[u]=true;
    for(register int i=head[u];i;i=edge[i].nxt)
    {
        E e=edge[i];
        if(vis[e.to]) continue;
        solve(e.to,e.cost,-1);
        S=siz[u],root=0,maxx[0]=n;
        Find_Center(e.to,u);
        dfs(root);
    }
    return;
}
int main()
{
//  freopen("read.txt","r",stdin);
//  freopen("output.txt","w",stdout);
    n=read(),m=read();
    for(register int i=1;i<n;i++)
    {
        int u=read(),v=read(),w=read();
        add_edge(u,v,w);
        add_edge(v,u,w); 
    }
    S=n,root=0,maxx[0]=n;
    Find_Center(1,0);    
    dfs(root);
    while(m--)
    {
        int k=read();
        if(mp[k]) puts("AYE");
        else puts("NAY");
    }
    return 0;
}

by 阿丑 @ 2022-01-21 13:09:56

@UperFicial dfs 里那个 S 应该设成以 u 的儿子为根的子树的大小，而不是以 u 为根的子树大小。

by UperFicial @ 2022-01-25 07:27:04

@阿丑 但是我改成了 siz[e.to] 好像也不行/wq

by 阿丑 @ 2022-01-25 09:03:31

@UperFicial 话说 solve 是不是 O(S^2) 的/yiw

by UperFicial @ 2022-01-27 20:13:39

@阿丑 我是 sb/kk

我再去改改，谢谢 ac/qq