WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
Wannafly挑战赛24 E.旅行
Wannafly挑战赛24 E.旅行

题目链接:https://www.nowcoder.com/acm/contest/186/E

题目大意

给定一颗N个点,每个点点权范围[0, 50]的树,给Q个询问,问树上从u到v的路径上,选择若干个点使其权值之和是K的倍数的方案数。

题解

离线所有询问,然后使用树分治处理所有询问。

对于一个询问,我们在对点x分治且x在路径上的时候回答它。
我们令F[p][k]为从x到p的路径上不选点x,其他随意权值和模K为k的方案数,那么对于的答案,我们只需要枚举是否选择点x即可合并得到。

代码

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int MAXN=2e5+50;
const int MOD=998244353;
struct Edge{
    int v, nxt;
    Edge(){}
    Edge(int v0, int n0){ v=v0; nxt=n0; }
}e[MAXN*2];
int head[MAXN], nume;

inline void addEdge(int u, int v){
    e[++nume]=Edge(v, head[u]);
    head[u]=nume;
    e[++nume]=Edge(u, head[v]);
    head[v]=nume;
}

bool vis[MAXN];
int siz[MAXN], RT, SIZ, mx[MAXN];
void dfs(int x, int from){
    siz[x]=1; mx[x]=0;
    for (int i=head[x]; i; i=e[i].nxt){
        int v=e[i].v; if (vis[v] || v==from) continue;
        dfs(v, x);
        siz[x]+=siz[v];
        if (siz[v]>mx[x]) mx[x]=siz[v];
    }
}
void dfs_rt(int x, int from){
    mx[x]=max(mx[x], SIZ-siz[x]);
    if (RT==0 || mx[x]<mx[RT]) RT=x;
    for (int i=head[x]; i; i=e[i].nxt){
        int v=e[i].v; if (v==from || vis[v]) continue;
        dfs_rt(v, x);
    }
}

inline void init(){
    memset(head, 0, sizeof(head));
    memset(vis, 0, sizeof(vis));
    nume=0;
}

struct Task{
    int idx, vec;
}task[MAXN];
vector<int> tasks[MAXN];

int n, K, Q;
int f[MAXN][55], ans[MAXN], val[MAXN];
int bel[MAXN], bran[MAXN], TL;
void dp(int x, int from){
    bel[x]=RT; bran[x]=TL;
    for (int k=0; k<K; k++)
        f[x][k]=(f[from][(k+K-val[x])%K]+f[from][k])%MOD;
    for (int i=head[x]; i; i=e[i].nxt){
        int v=e[i].v; if (v==from || vis[v]) continue;
        dp(v, x);
    }

    for (int t: tasks[x]){
        int v=task[t].vec^x, i=task[t].idx;
        if (bel[x]==bel[v] && bran[v]!=bran[x]){
            for (int k=0; k<K; k++){
                ans[i]=(ans[i]+1LL*f[x][k]*f[v][(K-k)%K]%MOD)%MOD;
                ans[i]=(ans[i]+1LL*f[x][k]*f[v][(K-k+K-val[RT])%K]%MOD)%MOD;
            }
        }
    }
}

void DAC(int x){
    dfs(x, 0);
    SIZ=siz[x]; RT=0;
    dfs_rt(x, 0);
    x=RT; vis[x]=true;

    for (int i=0; i<K; i++) f[x][i]=0; f[x][0]=1;
    for (int i=head[x]; i; i=e[i].nxt){
        int v=e[i].v; if (vis[v]) continue;
        ++TL; dp(v, x);
    }

    for (auto t: tasks[x]){
        int v=task[t].vec^x, i=task[t].idx;
        if (bel[v]==RT){
            for (int k=0; k<K; k++){
                ans[i]=(ans[i]+1LL*f[x][k]*f[v][(K-k)%K]%MOD)%MOD;
                ans[i]=(ans[i]+1LL*f[x][k]*f[v][(K-k+K-val[RT])%K]%MOD)%MOD;
            }
        }
    }

    for (int i=head[x]; i; i=e[i].nxt){
        int v=e[i].v; if (vis[v]) continue;
        DAC(v);
    }
}


int main(){
    //freopen("in.txt", "r", stdin);
    scanf("%d%d", &n, &K);
    for (int i=1, x, y; i<n; i++){ scanf("%d%d", &x, &y); addEdge(x, y); }
    for (int i=1; i<=n; i++) scanf("%d", &val[i]), val[i]%=K;
    scanf("%d", &Q);
    for (int i=1, x, y; i<=Q; i++){
        scanf("%d%d", &x, &y);
        task[i].vec=x^y; task[i].idx=i;
        tasks[x].emplace_back(i); tasks[y].emplace_back(i);
    }
    DAC(1);
    for (int i=1; i<=Q; i++) printf("%d\n", ans[i]);
    return 0;
}

赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

推荐文章

发表评论

textsms
account_circle
email

WNJXYKのBlog

Wannafly挑战赛24 E.旅行
题目链接:https://www.nowcoder.com/acm/contest/186/E 题目大意 给定一颗N个点,每个点点权范围$[0, 50]$的树,给Q个询问$<u, v>$,问树上从u到v的路径上,选择若干个点使其权值之…
扫描二维码继续阅读
2018-09-19
<--! http2https -->