湖南网站建设公司 地址磐石网络,生物商城网站建设,美食网站开发现状,宿州网站建设设计公司解析
很妙的一道题 看这两个南辕北辙的标签就知道这题不简单 看见dp思路还是得打开 一开始其实想到按边权排序了 但卡在了重构树上 遇到dp一定要敢想 勇于和图论等结合
考虑正解 按照边权升序排序 依次加边到图中 并查集维护连通性和集合内的边数 发现#xff0c;一个联通块…解析
很妙的一道题 看这两个南辕北辙的标签就知道这题不简单 看见dp思路还是得打开 一开始其实想到按边权排序了 但卡在了重构树上 遇到dp一定要敢想 勇于和图论等结合
考虑正解 按照边权升序排序 依次加边到图中 并查集维护连通性和集合内的边数 发现一个联通块合法当且仅当它在某个时刻是当前图的一个团 这个概念还是现查的…
考虑建一个重构树 显然所以合法的区间在树上对应的叶子的dfs序是连续的 可以通过dfs求出合法的区间并记录哪些区间可以进行转移 最后进行一遍朴素dp即可 由于合法的区间只会有On个所以均摊复杂度是n2n^2n2
代码
#includebits/stdc.h
using namespace std;
const int N1550;
const int mod998244353;
#define ll long long
ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();};while(isdigit(c)){xx*10c-0;cgetchar();};return x*f;
}int n,m;
struct node{int to,nxt;
}p[N1];
int fi[N1],cnt;
inline void addline(int x,int y){p[cnt](node){y,fi[x]};fi[x]cnt;return;
}struct edge{int x,y,w;
}e[N*N];
bool cmp(edge a,edge b){return a.wb.w;
}
int fa[N1],siz[N1],num[N1],tot,id,ls[N1],rs[N1],tim;
bool jd[N][N];
int find(int x){return xfa[x]?x:fa[x]find(fa[x]);}
void dfs(int x){if(fi[x]-1){siz[x]1;ls[x]rs[x]tim;jd[tim][tim]1;return;}for(int ifi[x];~i;ip[i].nxt){int top[i].to;dfs(to);siz[x]siz[to];if(!ls[x]) ls[x]ls[to];else rs[x]rs[to];}int ors[x]-ls[x]1;jd[ls[x]][rs[x]]num[x]o*(o-1)/2;//printf(x%d ls%d rs%d num%d\n,x,ls[x],rs[x],num[x]);return;
}
ll dp[N][N];
int main(){#ifndef ONLINE_JUDGE//freopen(a.in,r,stdin);//freopen(a.out,w,stdout);#endifmemset(fi,-1,sizeof(fi));cnt-1;nread();idn;for(int i1;in;i){for(int j1;jn;j){int xread();if(ij) e[tot](edge){i,j,x};}}for(int i1;in*2;i) fa[i]i;sort(e1,e1tot,cmp);for(int i1;itot;i){int xe[i].x,ye[i].y;xfind(x),yfind(y);if(xy){num[x];continue;}id;fa[x]fa[y]id;num[id]num[x]num[y]1;addline(id,x);addline(id,y);}dfs(id);dp[0][0]1;for(int i1;in;i){for(int k1;ki;k){if(!jd[k][i]) continue;for(int j1;jn;j){(dp[i][j]dp[k-1][j-1])%mod;}}}for(int i1;in;i) printf(%lld ,dp[n][i]);return 0;
}
/**/
