网站使用微信支付,宁国网络推广,网站制作建设案例,临夏州建设厅官方网站P3915 树的分解 DFS 维护每棵树的子树大小#xff0c;如果统计到 s i z x k siz_xk sizxk#xff0c;那么重新将 s i z x siz_x sizx 归零继续统计。 注意要输入完了再特判#xff0c;双向边要开两倍数组。 #include bits/stdc.h
using namespace std;const … P3915 树的分解 DFS 维护每棵树的子树大小如果统计到 s i z x k siz_xk sizxk那么重新将 s i z x siz_x sizx 归零继续统计。 注意要输入完了再特判双向边要开两倍数组。 #include bits/stdc.h
using namespace std;const int maxn2e55;
int head[maxn],A,B,siz[maxn],tot,cnt,N,K;
struct edge{int to,nxt;}e[maxn];void add(int x,int y){e[cnt](edge){y,head[x]},head[x]cnt;}void dfs(int x,int fa)
{siz[x]1;for(int ihead[x];i;ie[i].nxt) {if(e[i].tofa) continue;dfs(e[i].to,x),siz[x]siz[e[i].to];}if(siz[x]K) siz[x]0,tot;
}int main()
{int T;cinT;while(T--){cinNK;memset(head,0,sizeof head),cnt0,tot0,memset(siz,0,sizeof siz);memset(e,0,sizeof e);for(int i1,A,B;iN;i) cinAB,add(A,B),add(B,A);if(N%K){coutNOendl;continue;}dfs(1,0);if(totN/K) coutYESendl;else coutNOendl;}return 0;
}P2527 Panda的烦恼 sol. P3865 【模板】ST 表 Portal. 输出换行符 \n 比 endl 快。 #include bits/stdc.h
using namespace std;const int maxn1e55,maxm2e65;
int a[maxn],lg[maxn],f[maxn][25];inline int read()
{int x0,f1;char chgetchar();while (ch0||ch9){if (ch-) f-1;chgetchar();}while (ch0ch9){xx*10ch-48;chgetchar();}return x*f;
}void query(int l,int r)
{ int klg[r-l1];coutmax(f[l][k],f[r-(1k)1][k])\n;
}int main()
{ios::sync_with_stdio(false);int M,N;cinNM;lg[1]0;for(int i1;iN;i) f[i][0]read();for(int i2;iN;i) lg[i]lg[i/2]1;for(int j1;jlg[N];j)for(int i1;iN-(1j)1;i) f[i][j]max(f[i][j-1],f[i(1(j-1))][j-1]); while(M--){int lread(),rread();query(l,r);}return 0;
}
