萌新求助RE

P3806 【模板】点分治 1

Cierra_Runis @ 2019-12-20 23:36:29

#include<bits/stdc++.h>

using namespace std;

const int maxn = 10005;

const int maxk = 1000005;

int first[maxn << 1],next[maxn << 1],go[maxn << 1],tot,cost[maxn << 1];

void addedge(int u,int v,int w)
{
    next[++tot] = first[u];first[u] = tot;go[tot] = v;cost[tot] = w;
    next[++tot] = first[v];first[v] = tot;go[tot] = u;cost[tot] = w;
}

int n,m,rt,sum,cnt,x,y,z;

int tmp[maxn],siz[maxn],dis[maxn],maxp[maxn],q[105];

bool judge[maxk],ans[105],vis[maxn];

void getroot(int u,int f)
{
    siz[u] = 1;
    maxp[u] = 0;
    for(int e = first[u];e;e = next[e])
    {
        int v = go[e];
        if(v == f || vis[v]) continue;
        getroot(v,u);
        siz[u] += siz[v];
        if(siz[v] > maxp[u])maxp[u] = siz[v];
    }
    maxp[u] = max(maxp[u],sum - siz[u]);
    if(maxp[u] < maxp[rt]) rt = u;
}

void getdis(int u,int f)
{
    tmp[cnt++] = dis[u];
    for(int e = first[u];e;e = next[e])
    {
        int v = go[e];
        if(v == f || vis[v]) continue;
        dis[v] = dis[u] + cost[e];
        getdis(v,u);
    }
}

void solve(int u)
{
    queue<int> que;
    for(int e = first[u];e;e = next[e])
    {
        int v = go[e];
        if(vis[v]) continue;
        cnt = 0;
        dis[v] = cost[e];
        getdis(v,u);
        for(int i = 0;i < cnt;i++)
        {
            for(int j = 0;j < m;j++)
            {
                if(q[j] >= tmp[i])
                {
                    ans[j] |= judge[q[j] - tmp[i]];

                }
            }
        }
        for(int i = 0;i < cnt;i++)
        {
            que.push(tmp[i]);
            judge[tmp[i]] = true;
        }
    }
    while(!que.empty())
    {
        judge[que.front()] = false;
        que.pop();
    }
}

void divide(int u)
{
    vis[u] = judge[0] = true;
    solve(u);
    for(int e = first[u];e;e = next[e])
    {
        int v = go[e];
        if(vis[v]) continue;
        maxp[rt = 0] = sum = siz[v];
        getroot(v,0);
        getroot(rt,0);
        divide(rt);
    }
}

inline int read()
{
    char ch = getchar();
    int res = ch - 48;
    while((ch = getchar()) >= 48 && ch <= 57)
    {
        res = (res << 3) + (res << 1) + (ch - 48);
    }
    return res;
}

void write(int x)
{
    if(x >= 10) write(x / 10);
    putchar(x % 10 + 48);
}

int main()
{
    memset(first,0,sizeof(first));
    n = read();
    m = read();
    for(int i = 1;i < n;i++)
    {
        x = read();
        y = read();
        z = read();
        addedge(x,y,z);
     } 
    for(int i = 0;i < m;i++)
    {
        q[i] = read();
    }
    maxp[0] = sum = n;
    getroot(1,0);
    getroot(rt,0);
    divide(rt);
    for(int i = 0;i < m;i++)
    {
        if(ans[i] || q[i] == 0) puts("AYE");
        else puts("NAY");
    }
    return 0;
}

by Cierra_Runis @ 2019-12-21 11:21:34

问题已解决,我快读写炸了,我太弱了


|