请求加强数据

P3806 【模板】点分治 1

Missa @ 2022-01-10 11:18:59

RT，本人写点分治时经常忘掉 siz 数组存的到底是以谁为根的子树大小，昨晚终于过了该题，但今天被学校的该题卡了，这才意识到自己在分治时用的子树大小不是以分治传下去的重心为根，而是以计算重心时所选的根节点为根。

改了后节约了一半时间。改前 改后 可以看到，改后在分治前重新计算了子树大小。

希望数据能卡掉像我一样没有一开始理解透点分治的人。

by Missa @ 2022-01-10 11:21:58

顺便求调改后代码，在学校的数据WA了，把有判成了没有，不是标记数组的问题，该点询问路径长最大98。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int M = 40005;
struct edge{
    int to, nxt, w;
}e[M << 1];
int head[M], cnt1; bool vis[M], ans[M], f[10005005];
int u, v, w, k, root;
void link(int u, int v, int w){
    e[++cnt1].to = v; e[cnt1].w = w; e[cnt1].nxt = head[u]; head[u] = cnt1;
}
int siz[M], minn, n, dis[M], s, m, q[M], ss, d[M];
void calsiz(int u, int fa){
    siz[u] = 1; int m = 0;
    for(int i = head[u]; i; i = e[i].nxt){
        int v = e[i].to; if(v == fa || vis[v]) continue; calsiz(v, u);
        siz[u] += siz[v]; m = max(m, siz[v]);
    } m = max(m, ss - siz[u]);
    if(m <= minn) minn = m, root = u;
}
int get(int u, int siz){
    minn = 1e9; root = -1; ss = siz;
    return calsiz(u, 0), root;
}
void dfs(int u, int fa){
    dis[++s] = d[u];
    for(int i = head[u]; i; i = e[i].nxt){
        int v = e[i].to; if(v == fa || vis[v]) continue;
        d[v] = d[u] + e[i].w; dfs(v, u);
    }
}
queue<int> t;
void deal(int u){
    vis[u] = 1; f[0] = 1;
    for(int i = head[u]; i; i = e[i].nxt){
        int v = e[i].to; if(vis[v]) continue;
        d[v] = e[i].w; s = 0; dfs(v, u);
        for(int j = 1; j <= s; j++){
            for(int k = 1; k <= m; k++)
                if(dis[j] <= q[k]) ans[k] |= (f[q[k] - dis[j]]);
        }
        for(int j = 1; j <= s; j++)
            if(dis[j] <= 10000500 && !f[dis[j]]) f[dis[j]] = 1, t.push(dis[j]);
    } calsiz(u, 0); //这个帖子前面说的是这行
    while(!t.empty()) f[t.front()] = 0, t.pop();
    for(int i = head[u]; i; i = e[i].nxt){
        int v = e[i].to; if(vis[v]) continue;
        deal(get(v, siz[v]));
    }
}
int main(){
    scanf("%d %d", &n, &m);
    for(int i = 1; i < n; i++) scanf("%d %d %d", &u, &v, &w), link(u, v, w), link(v, u, w);
    for(int i = 1; i <= m; i++) scanf("%d", &q[i]);
    deal(get(1, n));
    for(int i = 1; i <= m; i++) printf("%s\n", ans[i] ? "Yes" : "No");
}

by GalaxyOier @ 2022-01-10 11:26:59

%%%

by 刘嘉琦 @ 2022-01-10 12:33:11

by 暗影之梦 @ 2022-01-10 12:40:29

%%%

by Missa @ 2022-01-10 13:29:31

？？？？？

您们都在在线卷题？

by NaOH_Frog @ 2022-01-10 14:19:03

被单调队列了/kk

by Missa @ 2022-01-10 15:13:23

@NaOH_Frog 已经被学弟学妹单调队列了

by 0000pnc @ 2022-01-10 23:23:32

%%%

|