九、十月刷题记录3

题记录3"/>

九、十月刷题记录3

cf600E dsu on tree模板

感觉就是树剖加强版。

//
// Created by Artist on 2021/10/16.
//#include<bits/stdc++.h>using namespace std;
typedef long long ll;
#define mkp make_pair
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(),x.end()
#define DB1(args...) do { cout << #args << " : "; dbg(args); } while (0)
#define endl '\n'void dbg() { std::cout << "  #\n"; }template<typename T, typename...Args>
void dbg(T a, Args...args) {std::cout << a << ' ';dbg(args...);
}void io() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); }
const int maxn = 1e5+5;int color[maxn];
ll res[maxn];
int son[maxn],sz[maxn];
int cnt[maxn]; // number of each color
vector<int> G[maxn];void dfs0(int u,int fa) {sz[u]=1;for(auto v:G[u]) {if(v-fa) {dfs0(v,u),sz[u]+=sz[v];if(sz[v]>sz[son[u]]) son[u]=v;}}
}int mx;
ll sm;
int pa;void count(int u,int fa,int flg) {cnt[color[u]]+=flg;if(cnt[color[u]]>mx) {mx = cnt[color[u]];sm = color[u];}else if(cnt[color[u]]==mx) sm += color[u];for(auto v:G[u]) if(v-fa&&v-pa) count(v,u,flg);
}void dfs(int u,int fa,bool del) {for(auto v:G[u]) if(v-fa&&v-son[u]) dfs(v,u,true);if(son[u]) dfs(son[u],u,false),pa=son[u];count(u,fa,1);pa=0;res[u] = sm;if(del) count(u,fa,-1),sm=mx=0;
}signed main() {io();int n;cin>>n;for(int i=1;i<=n;++i) {cin>>color[i];}for(int i=1;i<n;++i) {int x,y;cin>>x>>y;G[x].pb(y);G[y].pb(x);}dfs0(1,0);dfs(1,0,false);for(int i=1;i<=n;++i) {cout<<res[i]<<" ";}cout<<endl;
}

Easygoing Single Tune Circulation

做的第一道SAM

//
// Created by Artist on 2021/10/19.
//#include<bits/stdc++.h>using namespace std;
typedef long long ll;
#define mkp make_pair
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(),x.end()
#define DB1(args...) do { cout << #args << " : "; dbg(args); } while (0)
#define endl '\n'void dbg() { std::cout << "  #\n"; }template<typename T, typename...Args>
void dbg(T a, Args...args) {std::cout << a << ' ';dbg(args...);
}void io() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); }
const int maxn = 1e6+4;
struct SAM {int mxlen[maxn<<1],link[maxn<<1],nt[maxn<<1][26];int sz,last,len;void init() {memset(nt[0],0,sizeof(nt[0]));mxlen[0]=0;link[0]=-1;sz=1;last=0;}void extend(int c) {c-='a';int cur=sz++;mxlen[cur]=mxlen[last]+1;int p=last;memset(nt[cur],0,sizeof(nt[cur]));while(p!=-1&&!nt[p][c]) {nt[p][c]=cur;p=link[p];}if(p==-1) link[cur]=0;else {int q=nt[p][c];if(mxlen[p]+1==mxlen[q]) link[cur]=q;else {int clone=sz++;mxlen[clone]=mxlen[p]+1;memcpy(nt[clone],nt[q],sizeof(nt[q]));link[clone]=link[q];while(p!=-1&&nt[p][c]==q) {nt[p][c]=clone;p=link[p];}link[q]=link[cur]=clone;}}last=cur;}bool query(string s) {int p=0;for(int i=0;i<s.size();++i) {int c=s[i]-'a';if(!nt[p][c]) return 0;p=nt[p][c];}return 1;}
}sam;struct Trie {int tree[maxn][30];int color[maxn];int k=1;int newnode() {memset(tree[k],0,sizeof(tree[k]));color[k]=0;return k++;}void init() {color[0]=0;memset(tree[0],0,sizeof(tree[0]));k=1;}void insert(string a) {int p=0;int len=a.size();for(int i=0;i<len;++i) {int c=a[i]-'a';if(!tree[p][c]) tree[p][c]=newnode();p=tree[p][c];}color[p]++;}int query(string a) {int p=0;int len=a.size();for(int i=0;i<len;++i) {int c=a[i]-'a';if(!tree[p][c]) return 0;p=tree[p][c];}return color[p];}
}trie;const int maxm = 1e5+5;
string s[maxm];string get_min(string s) {string t;int p=26,pos=0;for(int i=0;i<s.size();++i) {if(s[i]-'a'<=p) p=s[i]-'a',pos=i;}t=s.substr(pos);t+=s.substr(0,pos);return t;
}signed main() {io();int T;cin>>T;int cas=0;while(T--) {sam.init();trie.init();cout<<"Case #"<<++cas<<":"<<endl;int n;cin>>n;for(int i=0;i<n;++i) {cin>>s[i];string t=get_min(s[i]);trie.insert(t);}for(int i=0;i<n;++i) {sam.last=0;for(int j=0;j<s[i].size();++j) sam.extend(s[i][j]);for(int j=0;j<s[i].size();++j) sam.extend(s[i][j]);}int m;cin>>m;while(m--) {string a;cin>>a;if(sam.query(a)) {cout<<"YES"<<endl;continue;}int pos=a.size();for(int i=1;i<pos;++i) {if(a[i]==a[0]) {pos=i;break;}}string t=a.substr(0,pos);string tt=get_min(t);if(trie.query(tt)) {string p;for(int i=0;i<a.size();++i) p+=t[i%t.size()];if(p==a) {cout<<"YES"<<endl;continue;}}cout<<"NO"<<endl;}}
}

NC15254 白兔的刁难

单位根反演

//
// Created by Artist on 2021/10/20.
//#include<bits/stdc++.h>using namespace std;
typedef long long ll;
#define mkp make_pair
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(),x.end()
#define DB1(args...) do { cout << #args << " : "; dbg(args); } while (0)
#define endl '\n'void dbg() { std::cout << "  #\n"; }template<typename T, typename...Args>
void dbg(T a, Args...args) {std::cout << a << ' ';dbg(args...);
}void io() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); }const ll p=998244353;
const ll p2=998244352;
const ll g=3;
const int maxn = 2e6+6;
ll qpow(ll a,ll n) {ll ans=1;while(n) {if(n&1) ans=ans*a%p;a=a*a%p;n>>=1;}return ans;
}string s;
ll a[maxn];
int rev[maxn];void ntt(ll *a,int n,int t) {for(int i=1;i<n;++i) {rev[i]=(rev[i>>1]>>1)|(i&1?n>>1:0);if(i>rev[i]) swap(a[i],a[rev[i]]);}for(int i=2;i<=n;i<<=1) {int wn=qpow(g,(p-1)/i);if(t==-1) wn=qpow(wn,p-2);for(int j=0;j<n;j+=i) {int w=1;for(int k=j;k<j+i/2;++k) {int u=a[k];int v=a[k+i/2]*w%p;a[k]=(u+v)%p;a[k+i/2]=(u-v+p)%p;w=1ll*w*wn%p;}}}if(t==-1) {ll inv=qpow(n,p-2);for(int i=0;i<n;++i) a[i]=a[i]*inv%p;}
}signed main() {cin>>s;int n=0,k;cin>>k;int len=s.length();for(int i=0;i<len;++i) {n=(1ll*n*10+s[i]-'0')%p2;}ll w=qpow(g,(p-1)/k);ll now=1;for(int i=0;i<k;++i) {a[i]=qpow(now+1,n);now=now*w%p;}ntt(a,k,-1);ll ans=0;for(int i=0;i<k;++i) ans=ans^a[i];cout<<ans<<endl;
}

最小瓶颈路

Kruskal 生成树 + rmq

/
// Created by Artist on 2021/10/21.
//#include<bits/stdc++.h>using namespace std;
typedef long long ll;
#define mkp make_pair
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(),x.end()
#define DB1(args...) do { cout << #args << " : "; dbg(args); } while (0)
#define endl '\n'void dbg() { std::cout << "  #\n"; }template<typename T, typename...Args>
void dbg(T a, Args...args) {std::cout << a << ' ';dbg(args...);
}void io() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); }
int n,m;const int maxn = 3e5+5;
const int mod = 1e9+7;int A,B,C,P;
inline int rnd() {return A=(A*B+C)%P;
}struct nod{int u,v;ll w;bool operator < (const nod &b) const {return w<b.w;}
}ed[maxn];vector<int> G[maxn];ll val[maxn];
int fa[maxn];
int dfn,id[maxn],rk[maxn];
// 每个点第一次出现的dfn
int find(int x) {return fa[x]=fa[x]==x?x:find(fa[x]);
}// 二叉树可以直接中序遍历
void dfs(int u) {if(G[u].size()) dfs(G[u][0]);id[u]=++dfn,rk[dfn]=u;if(G[u].size()) dfs(G[u][1]);
}
int mx[20][maxn],lg[maxn];
struct RMQ {void build() {lg[0]=-1;for(int i=1;i<=n;++i) {lg[i]=lg[i-1]+(i&i-1?0:1);mx[0][i]=val[rk[i]];}for(int j=1;j<=lg[n];++j) for(int i=1;i<=n-(1<<j)+1;++i)mx[j][i]=max(mx[j-1][i],mx[j-1][i+(1<<j-1)]);}int query(int l,int r) {int k=lg[r-l+1];return max(mx[k][l],mx[k][r-(1<<k)+1]);}
};signed main() {scanf("%d%d",&n,&m);for(int i=1;i<=m;++i) {scanf("%d%d%lld",&ed[i].u,&ed[i].v,&ed[i].w);}sort(ed+1,ed+1+m);for(int i=1;i<=2*n-1;++i) fa[i]=i;int cnt=0,orin=n;for(int i=1;i<=m;++i) {int u=ed[i].u,v=ed[i].v;u=find(u),v=find(v);if(u==v) continue;cnt++,n++;val[n] = ed[i].w;G[n].pb(u);G[n].pb(v);fa[u]=fa[v]=n;if(cnt==orin-1) break;}dfs(n);int q;scanf("%d",&q);scanf("%d%d%d%d",&A,&B,&C,&P);ll ans=0;RMQ rmq;rmq.build();while(q--) {
//        DB1(rnd(),rnd());int u=rnd()%orin+1,v=rnd()%orin+1;
//        DB1(u,v);
//        int u,v;if(id[u]>id[v]) swap(u,v);
//        DB1(rmq.query(id[u],id[v]));ans=(ans+rmq.query(id[u],id[v]))%mod;}printf("%d\n",ans);
}

UOJ 393. 【NOI2018】归程

Kruskal生成树+最短路
利用性质：生成树子树都满足路径最大/小权重小于根权重。
在子树中找最短路即可。

//
// Created by Artist on 2021/10/21.
//#include<bits/stdc++.h>using namespace std;
typedef long long ll;
#define mkp make_pair
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(),x.end()
#define DB1(args...) do { cout << #args << " : "; dbg(args); } while (0)
#define endl '\n'void dbg() { std::cout << "  #\n"; }template<typename T, typename...Args>
void dbg(T a, Args...args) {std::cout << a << ' ';dbg(args...);
}void io() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); }
const int maxn = 2e5+5;
const int maxm = 4e5+5;
const ll inf = 1e18;
struct node {int u,v,l,a;bool operator < (const node &b) const {return a > b.a;}
}ed[maxm];
int fa[maxn<<1];
ll mn[maxn<<1];
int find(int x) {return fa[x]=fa[x]==x?x:find(fa[x]);
}
ll dis[maxn]; // 每个结点的距离
int val[maxn<<1]; // kruskal生成树中节点的权值
vector<int> G[maxn<<1];
int dep[maxn<<1],f[22][maxn<<1];
ll dfs(int u,int pa) {dep[u]=dep[pa]+1;f[0][u]=pa;if(G[u].size()==0) return mn[u]=dis[u];return mn[u]=min(dfs(G[u][0],u),dfs(G[u][1],u));
}ll solve(int y,int p) {int x=1;if(dep[x]<dep[y]) {for(int j=20;~j;--j)if(dep[f[j][y]]>=dep[x] && f[j][y] && val[f[j][y]]>p) y=f[j][y];if(!f[0][y]||x==y||val[f[0][y]]<=p) return mn[y];} else {for(int j=20;~j;--j)if(dep[f[j][x]]>=dep[y] && f[j][x]) x=f[j][x];if(x==y) return mn[x];}for(int j=20;~j;--j)if(f[j][x]!=f[j][y] && f[j][y] && val[f[j][y]]>p)x=f[j][x],y=f[j][y];if(val[f[0][y]]<=p) return mn[y];else return mn[f[0][y]];
}struct nod {ll dis;int u;bool operator > (const nod &b) const {return dis>b.dis;}
};
vector<nod> G2[maxn];
int vis[maxn];
priority_queue<nod,vector<nod>,greater<nod> > pq;void dijkstra(int n) {for(int i=1;i<=n;++i) dis[i]=inf;dis[1]=0;pq.push({0,1});while(pq.size()) {nod cur=pq.top();pq.pop();if(vis[cur.u]) continue;vis[cur.u]=1;for(auto o:G2[cur.u]) {int v=o.u,w=o.dis;if(dis[v]>dis[cur.u]+w) {dis[v] = dis[cur.u]+w;pq.push({dis[v],v});}}}
}signed main() {io();int t;cin>>t;while(t--) {int n,m;cin>>n>>m;for(int i=1;i<=2*n-1;++i) {G[i].clear();fa[i]=i;}for(int i=1;i<=n;++i) {G2[i].clear();vis[i]=0;}for(int i=1;i<=m;++i) {cin>>ed[i].u>>ed[i].v>>ed[i].l>>ed[i].a;G2[ed[i].u].pb({ed[i].l,ed[i].v});G2[ed[i].v].pb({ed[i].l,ed[i].u});}dijkstra(n);sort(ed+1,ed+1+m);int cnt=0,orin=n;for(int i=1;i<=m;++i) {int u=ed[i].u,v=ed[i].v,w=ed[i].a;u=find(u),v=find(v);if(u==v) continue;++n,++cnt;G[n].pb(u);G[n].pb(v);val[n]=w;fa[u]=fa[v]=n;if(cnt==orin-1) break;}dfs(n,0);for(int j=1;j<=20;++j) for(int i=1;i<=n;++i) f[j][i]=f[j-1][f[j-1][i]];int q,k,s;cin>>q>>k>>s;ll ans=0;while(q--) {int v0,p0;cin>>v0>>p0;int v=(1ll*v0+ans*k-1)%orin+1,p=(1ll*p0+ans*k)%(s+1);
//           DB1(v,p);ans=solve(v,p);cout<<ans<<endl;}}
}