2020-2021:teams:legal_string:jxm2001:静态点分治
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:静态点分治 [2020/06/05 23:21] jxm2001 |
2020-2021:teams:legal_string:jxm2001:静态点分治 [2020/07/26 15:53] (当前版本) jxm2001 ↷ 页面2020-2021:teams:legal_string:静态点分治被移动至2020-2021:teams:legal_string:jxm2001:静态点分治 |
||
|---|---|---|---|
| 行 46: | 行 46: | ||
| } | } | ||
| void solve(int u){ | void solve(int u){ | ||
| + | int cur_sz=tot_sz; | ||
| vis[u]=true;query(u); | vis[u]=true;query(u); | ||
| for(int i=head[u];i;i=edge[i].next){ | for(int i=head[u];i;i=edge[i].next){ | ||
| 行 51: | 行 52: | ||
| if(vis[v]) | if(vis[v]) | ||
| continue; | continue; | ||
| - | tot_sz=sz[v];root_sz=inf; | + | tot_sz=sz[v]>sz[u]?cur_sz-sz[u]:sz[v];root_sz=MAXN; |
| find_root(v,u); | find_root(v,u); | ||
| solve(root); | solve(root); | ||
| 行 84: | 行 85: | ||
| <hidden 代码> | <hidden 代码> | ||
| <code cpp> | <code cpp> | ||
| - | #include <cstdio> | ||
| - | #include <cctype> | ||
| - | #include <vector> | ||
| - | #define _for(i,a,b) for(int i=(a);i<(b);++i) | ||
| - | using namespace std; | ||
| - | inline int read_int(){ | ||
| - | int t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| const int MAXN=1e4+5,inf=1e7+5; | const int MAXN=1e4+5,inf=1e7+5; | ||
| struct Edge{ | struct Edge{ | ||
| 行 139: | 行 129: | ||
| void query(int u){ | void query(int u){ | ||
| sd.clear(); | sd.clear(); | ||
| + | mark[0]=true; | ||
| for(int i=head[u];i;i=edge[i].next){ | for(int i=head[u];i;i=edge[i].next){ | ||
| d.clear(); | d.clear(); | ||
| 行 162: | 行 153: | ||
| } | } | ||
| void solve(int u){ | void solve(int u){ | ||
| - | vis[u]=mark[0]=true;query(u); | + | int cur_sz=tot_sz; |
| + | vis[u]=true;query(u); | ||
| for(int i=head[u];i;i=edge[i].next){ | for(int i=head[u];i;i=edge[i].next){ | ||
| int v=edge[i].to; | int v=edge[i].to; | ||
| if(vis[v]) | if(vis[v]) | ||
| continue; | continue; | ||
| - | tot_sz=sz[v];root_sz=inf; | + | tot_sz=sz[v]>sz[u]?cur_sz-sz[u]:sz[v];root_sz=MAXN; |
| find_root(v,u); | find_root(v,u); | ||
| solve(root); | solve(root); | ||
| 行 209: | 行 201: | ||
| <hidden 代码> | <hidden 代码> | ||
| <code cpp> | <code cpp> | ||
| - | #include <cstdio> | ||
| - | #include <cctype> | ||
| - | #include <vector> | ||
| - | #define _for(i,a,b) for(int i=(a);i<(b);++i) | ||
| - | using namespace std; | ||
| - | inline int read_int(){ | ||
| - | int t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| const int MAXN=2e5+5,inf=1e6+5; | const int MAXN=2e5+5,inf=1e6+5; | ||
| struct Edge{ | struct Edge{ | ||
| 行 285: | 行 266: | ||
| } | } | ||
| void solve(int u){ | void solve(int u){ | ||
| + | int cur_sz=tot_sz; | ||
| vis[u]=true;query(u); | vis[u]=true;query(u); | ||
| for(int i=head[u];i;i=edge[i].next){ | for(int i=head[u];i;i=edge[i].next){ | ||
| 行 290: | 行 272: | ||
| if(vis[v]) | if(vis[v]) | ||
| continue; | continue; | ||
| - | tot_sz=sz[v];root_sz=MAXN; | + | tot_sz=sz[v]>sz[u]?cur_sz-sz[u]:sz[v];root_sz=MAXN; |
| find_root(v,u); | find_root(v,u); | ||
| solve(root); | solve(root); | ||
| 行 372: | 行 354: | ||
| <hidden 代码> | <hidden 代码> | ||
| <code cpp> | <code cpp> | ||
| - | #include <cstdio> | ||
| - | #include <cctype> | ||
| - | #include <vector> | ||
| - | #define _for(i,a,b) for(int i=(a);i<(b);++i) | ||
| - | using namespace std; | ||
| - | typedef long long LL; | ||
| - | inline int read_int(){ | ||
| - | int t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| - | inline void write(LL x){ | ||
| - | register char c[21],len=0; | ||
| - | if(!x)return putchar('0'),void(); | ||
| - | if(x<0)x=-x,putchar('-'); | ||
| - | while(x)c[++len]=x%10,x/=10; | ||
| - | while(len)putchar(c[len--]+48); | ||
| - | } | ||
| - | inline void space(LL x){write(x),putchar(' ');} | ||
| - | inline void enter(LL x){write(x),putchar('\n');} | ||
| const int MAXN=1e5+5; | const int MAXN=1e5+5; | ||
| struct Edge{ | struct Edge{ | ||
| 行 495: | 行 456: | ||
| } | } | ||
| void solve(int u){ | void solve(int u){ | ||
| + | int cur_sz=tot_sz; | ||
| vis[u]=true;query(u); | vis[u]=true;query(u); | ||
| for(int i=head[u];i;i=edge[i].next){ | for(int i=head[u];i;i=edge[i].next){ | ||
| 行 500: | 行 462: | ||
| if(vis[v]) | if(vis[v]) | ||
| continue; | continue; | ||
| - | tot_sz=sz[v];root_sz=MAXN; | + | tot_sz=sz[v]>sz[u]?cur_sz-sz[u]:sz[v];root_sz=MAXN; |
| find_root(v,u); | find_root(v,u); | ||
| solve(root); | solve(root); | ||
2020-2021/teams/legal_string/jxm2001/静态点分治.1591370465.txt.gz · 最后更改: 2020/06/05 23:21 由 jxm2001
