题解：P17409 【MX-X31-T5】「FAOI-R14」noiday2t3 数据

· · 题解

Let's discover something new and exciting!

前置介绍

熟悉平面图相关内容可以跳过。

什么是平面图？就是可以把一张图每个顶点在平面上选个位置，使得边不相交的图。

根据欧拉公式，设点数、边数、所有边将整个平面划分成的面数（包括外无限面）分别为 n,m,f，对于一个连通平面图，有 n-m+f=2。可以通过从一个生成树连边归纳证明。

点数若 \ge 3，则对于每个面，其边界至少有 3 条边，而每条边会被两侧平面各数一次，故 2m\ge 3f，代入得 m\le 3n-6，即本题数据范围。

解法

因为 m\le 3n-6，所以总度数 \le 6n-12，因此对于任何平面度，存在度数 \le 5 的节点。

考虑本题不带修改怎么做，简单完了，对于每个节点 u 计算答案，相当于对所有邻点跑 0/1 背包：

考虑一个给边定向的 trick，修改 x 时暴力修改从 x 每条出边连向点的 f_v，即撤销一次背包再加入一次。查询 x 时剩下 x 出边连向的点没有计算贡献，设其数量为 d，尝试暴力 2^d 枚举选的集合 S，答案为 \sum_S f_{x,y-\sum_{v\in S}a_v}。

我们只要找到一个方案让每个点出度够小即可接受，到这里就好做了，每次删去度数 \le 5 的点并将其还连着的边定向为出边，然后删除这个点，即可做到。

时间复杂度 O(mV+q_1DV+q_22^D)，其中 V=5000,D=5。

::::info[code]

#include<bits/MPLN.h>
using namespace std;
const int MOD=998244353;
inline void upd(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}
inline void dec(int &x,int y){x-=y;if(x<0)x+=MOD;}
int n,m,q1,q2,d[5010],a[5010];
vector<int> e[5010];
int out[5010][6],tp[5010];
bool vis[5010];
int f[5010][5010],sum[32];
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin>>n>>m>>q1>>q2;
    queue<int> q;
    for(int i=1;i<=n;i++){
        cin>>d[i];
        for(int j=1,x;j<=d[i];j++) cin>>x,e[i].push_back(x);
        if(d[i]<=5) q.push(i);
    }
    while(!q.empty()){
        int x=q.front(); q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int v:e[x])if(!vis[v]){
            out[x][tp[x]++]=v;
            if((--d[v])<=5) q.push(v);
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=0;j<=5000;j++) f[i][j]=1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        for(int t=0,x=out[i][t];t<tp[i];t++,x=out[i][t])
            for(int j=5000;j>=a[i];j--)
                upd(f[x][j],f[x][j-a[i]]);
    }
    int T=q1+q2;
    while(T--){
        int op,x,y; cin>>op>>x>>y;
        if(op==1){
            for(int t=0,v=out[x][t];t<tp[x];t++,v=out[x][t])
                for(int j=a[x];j<=5000;j++)
                    dec(f[v][j],f[v][j-a[x]]);
            a[x]=y;
            for(int t=0,v=out[x][t];t<tp[x];t++,v=out[x][t])
                for(int j=5000;j>=a[x];j--)
                    upd(f[v][j],f[v][j-a[x]]);
        }else{
            int ans=0;
            for(int i=0;i<(1<<tp[x]);i++){
                sum[i]=(!i)?(0):(sum[i-(i&-i)]+a[out[x][__builtin_ctz(i)]]);
                if(sum[i]<=y) upd(ans,f[x][y-sum[i]]);
            }
            cout<<ans<<'\n';
        }
    }
    return 0;
}

::::