题解：
https://files.cnblogs.com/files/clrs97/2022ICPCHangzhouTutorial.pdf
Code：
A. Modulo Ruins the Legend
#include<bits/stdc++.h>
using namespace std;
int n,m;
int exgcd(int a,int b,int &x,int &y)
{
if(!b)
{
x=1,y=0;
return a;
}
int g=exgcd(b,a%b,y,x);
y-=a/b*x;
return g;
}
int main()
{
scanf("%d%d",&n,&m);
int s=0;
for(int i=1,x;i<=n;i++)
{
scanf("%d",&x);
s=(s+x)%m;
}
//an - bm = g
int a,b;
int t=n%2==1?n:n/2;
int g=exgcd(t,m,a,b);
//a * n
int k=s%g,x=(k-s)/g;
x=1ll*x*a%m;
if(x<0)
x+=m;
printf("%d\n",k);
if(n%2==0)
{
if(x%2==0)
printf("%d %d\n",x/2,0);
else
printf("%d %d\n",(((x-1)/2-n/2)%m+m)%m,1%m);
}
else
printf("%d %d\n",x,0);
}
B. Useful Algorithm
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+1e3+7;
int n,m,q;
int c[N],d[N],w[21];
int cnt,rt[21];
struct Tree{
#define ls (x<<1)
#define rs (x<<1|1)
struct T{
int mx;
int v[2];
};
vector<T>t;
void update(int x)
{
t[x].mx=max({t[ls].mx,t[rs].mx,t[ls].v[1]+t[rs].v[0]});
t[x].v[0]=max(t[ls].v[0],t[rs].v[0]);
t[x].v[1]=max(t[ls].v[1],t[rs].v[1]);
}
void build(int x,int l,int r)
{
if(x==1)
t.resize(r*4+1);
if(l==r)
{
t[x].mx=-2e9;
t[x].v[0]=t[x].v[1]=-1e9;
return;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
update(x);
}
void change(int x,int p,int a,int b,int l,int r)
{
if(l==r)
{
t[x].v[a]=b;
t[x].mx=t[x].v[0]+t[x].v[1];
return;
}
int mid=(l+r)>>1;
if(p<=mid)
change(ls,p,a,b,l,mid);
else
change(rs,p,a,b,mid+1,r);
update(x);
}
#undef ls
#undef rs
}tr[21];
struct MXH{
priority_queue<int>q,dq;
void insert(int x)
{
q.push(x);
}
void erase(int x)
{
dq.push(x);
}
int top()
{
while(q.size()&&dq.size())
{
if(q.top()==dq.top())
q.pop(),dq.pop();
else
break;
}
if(q.size())
return q.top();
else
return -1e9;
}
};
vector<MXH>s[21];
int get(MXH &s)
{
return s.top();
}
ll calc()
{
ll ret=0;
for(int i=1;i<=m;i++)
ret=max(ret,1ll*tr[i].t[1].mx*w[i]);
return ret;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m>>q;
for(int i=1;i<=m;i++)
cin>>w[i];
for(int i=1;i<=n;i++)
cin>>c[i];
for(int i=1;i<=n;i++)
cin>>d[i];
for(int i=1;i<=m;i++)
s[i].resize(1<<i);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
s[j][c[i]%(1<<j)].insert(d[i]);
for(int i=1;i<=m;i++)
{
tr[i].build(1,0,1<<i);
for(int j=0;j<(1<<i);j++)
{
int mx=get(s[i][j]);
if(mx<0)
continue;
tr[i].change(1,j,0,mx,0,(1<<i));
tr[i].change(1,(1<<i)-j,1,mx,0,(1<<i));
}
}
ll ans=calc();
cout<<ans<<"\n";
while(q--)
{
ll x,u,v;
cin>>x>>u>>v;
x^=ans,u^=ans,v^=ans;
for(int i=1;i<=m;i++)
{
int p=c[x]%(1<<i);
s[i][p].erase(d[x]);
int mx=get(s[i][p]);
tr[i].change(1,p,0,mx,0,(1<<i));
tr[i].change(1,(1<<i)-p,1,mx,0,(1<<i));
}
c[x]=u;
d[x]=v;
for(int i=1;i<=m;i++)
{
int p=c[x]%(1<<i);
s[i][p].insert(d[x]);
int mx=get(s[i][p]);
tr[i].change(1,p,0,mx,0,(1<<i));
tr[i].change(1,(1<<i)-p,1,mx,0,(1<<i));
}
ans=calc();
cout<<ans<<"\n";
}
}
C. No Bug No Game
#include<cstdio>
const int N=3005,M=3005,V=15;
int n,m,sum,i,j,k,x,t,sz,full,size[N],w[N][V],f[2][M];
inline void up(int&a,int b){a<b?(a=b):0;}
int main(){
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%d",&size[i]);
sum+=size[i];
for(j=1;j<=size[i];j++)scanf("%d",&w[i][j]);
}
if(m>sum)m=sum;
for(j=0;j<2;j++)for(k=0;k<=m;k++)f[j][k]=-1;
f[0][0]=0;
for(i=1;i<=n;i++){
sz=size[i];
full=w[i][size[i]];
for(j=1;~j;j--)for(k=m;~k;k--){
t=f[j][k];
if(t<0)continue;
if(k+sz<=m)up(f[j][k+sz],t+full);
if(j)continue;
for(x=0;x<=sz&&k+x<=m;x++)up(f[1][k+x],t+w[i][x]);
}
}
printf("%d",f[1][m]);
}
D. Money Game
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+1e3+7;
int n,a[N];
int main()
{
scanf("%d",&n);
long long s=0;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),s+=a[i];
for(int i=1;i<=n;i++)
printf("%.15lf%c",1.0*s*((i==1)+1)/(n+1)," \n"[i==n]);
}
E. Oscar is All You Need
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+1e2+7;
int T,n;
int a[N],b[N],c;
typedef pair<int,int> pii;
vector<pii>ans;
void opt(int x,int y)
{
assert(x>0&&y>0&&x+y<n);
c=0;
for(int i=n-y+1;i<=n;i++)
b[++c]=a[i];
for(int i=x+1;i<=n-y;i++)
b[++c]=a[i];
for(int i=1;i<=x;i++)
b[++c]=a[i];
for(int i=1;i<=n;i++)
a[i]=b[i];
ans.push_back({x,y});
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
ans.clear();
if(n==3)
{
vector<pii>ans;
if(a[1]>a[3])
opt(1,1);
}
else
{
if(a[1]!=1)
{
int pos=1;
for(int i=2;i<=n;i++)
if(a[i]==1)
pos=i;
if(pos==2)
{
opt(2,1);
opt(1,1);
}
else
opt(1,n-pos+1);
assert(a[1]==1);
}
for(int i=2;i<=n-2;i++)
{
if(a[i]==i)
continue;
int pos=-1;
for(int j=i+1;j<=n;j++)
if(a[j]==i)
pos=j;
assert(pos!=-1);
if(pos!=i+1)
{
opt(i-1,n-pos+2);
opt(1,i-1);
}
else
{
opt(i-1,1);
opt(2,i-1);
}
}
if(a[n-1]==n)
{
//1, 2, ..., n - 2, n, n - 1
opt(1,1);
//n-1 , 2, ..., n - 2, n, 1
opt(n-2,1);
//1, n, n-1, 2, ..., n - 2
opt(2,n-3);
//2, ..., n-2, n-1, 1, n
opt(n-3,1);
//n, n-1, 1, 2, ..., n-2
opt(1,n-2);
//1, 2, ..., n-2, n-1, n
}
for(int i=1;i<=n;i++)
assert(a[i]==i);
}
printf("%d\n",(int)ans.size());
for(auto [x,y]:ans)
printf("%d %d\n",x,y);
}
}
F. Da Mi Lao Shi Ai Kan De
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
map<string, int>mp;
int main()
{
ios_base::sync_with_stdio(false);
int Tcase; cin>>Tcase;
while(Tcase--)
{
int num=0;
cin>>n;
for(int i=1;i<=n;i++)
{
string str; cin>>str;
int L=str.size();
int ok=0;
for(int j=0;j+2<L;j++)
{
if(str[j]=='b' && str[j+1]=='i' && str[j+2]=='e') ok=1;
}
if( ok && mp.count(str) > 0 )
ok=0;
if(ok)
{
cout<<str<<'\n';
mp[str]=1;
num++;
}
}
if(num==0)
{
cout<<"Time to play Genshin Impact, Teacher Rice!\n";
}
}
return 0;
}
G. Subgraph Isomorphism
#include <bits/stdc++.h>
using namespace std;
vector<int> G[100005], sta;
int n, m;
bool vis[100005];
int dfs(int v, int p) {
vis[v] = true;
sta.push_back(v);
for(auto u : G[v]) {
if(u == p) continue;
if(vis[u]) return u;
else {
int ret = dfs(u, v);
if(ret != -1) return ret;
}
}
sta.pop_back();
return -1;
}
map<vector<int>,int>MAP;
int cnt;
int hs[100005];
vector<int>tmp;
void gen_hs(int v, int p)
{
int deg=0;
for(auto u : G[v]) {
if(u == p || vis[u]) continue;
gen_hs(u, v);
deg++;
}
tmp.resize(deg);
deg=0;
for(auto u : G[v]) {
if(u == p || vis[u]) continue;
tmp[deg++]=hs[u];
}
sort(tmp.begin(),tmp.end());
int&o=MAP[tmp];
if(!o)o=++cnt;
hs[v]=o;
}
void solve() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
G[i].clear();
for(int i = 0; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
if(m > n) {
printf("NO\n");
return;
}
if(m < n) {
printf("YES\n");
return;
}
for(int i = 1; i <= n; i++)
vis[i] = false;
sta.clear();
int r = dfs(1, 0);
for(int i = 0; i < (int)sta.size(); i++)
if(sta[i] == r) {
sta.erase(sta.begin(), sta.begin() + i);
break;
}
for(int i = 1; i <= n; i++)
vis[i] = false;
for(auto v : sta)
vis[v] = true;
cnt=0;
MAP.clear();
for(auto v : sta)
gen_hs(v, 0);
for(int i = 0; i < (int)sta.size(); i++)
if(hs[sta[i]] != hs[sta[(i + 2) % (int)sta.size()]]) {
printf("NO\n");
return;
}
printf("YES\n");
}
int main() {
int T;
scanf("%d", &T);
while(T --) solve();
return 0;
}
H. RPG Pro League
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int,int>P;
typedef long long ll;
const int N=100005;
int n,q,i,j,S,x,y,mask[N],cost[N],pool[N],is[N];
int clim,num,adj[5],cnt[9],bound[257];
ll ans;
priority_queue<P>used[9];
priority_queue<P,vector<P>,greater<P> >unused[9];
struct Lim{int mask,cap;}lim[17];
inline int cmp(int x,int y){return cost[x]<cost[y];}
inline bool check(){
for(int i=1;i<=clim;i++){
int mask=lim[i].mask,cap=lim[i].cap;
for(int j=1;j<8;j++)if(mask>>j&1){
cap-=cnt[j];
if(cap<=0)break;
}
if(cap>0)return 0;
}
return 1;
}
inline int getused(int S){
while(!used[S].empty()){
P t=used[S].top();
if(!is[t.second]||cost[t.second]!=t.first){
used[S].pop();
continue;
}
return t.second;
}
return 0;
}
inline int getunused(int S){
while(!unused[S].empty()){
P t=unused[S].top();
if(is[t.second]||cost[t.second]!=t.first){
unused[S].pop();
continue;
}
return t.second;
}
return 0;
}
inline void modify(int x,int y){
int S=mask[x],i,best,who=0;
if(is[x]){
ans+=y-cost[x];
if(y<=cost[x]){
used[S].push(P(cost[x]=y,x));
return;
}
best=cost[x]=y;
cnt[S]--;
for(i=1;i<8;i++){
y=getunused(i);
if(!y)continue;
if(cost[y]>=best)continue;
cnt[mask[y]]++;
if(check())best=cost[y],who=y;
cnt[mask[y]]--;
}
if(who){
is[x]=0;
unused[S].push(P(cost[x],x));
ans+=best-cost[x];
cnt[mask[who]]++;
is[who]=1;
used[mask[who]].push(P(cost[who],who));
}else{
cnt[S]++;
used[S].push(P(cost[x],x));
}
}else{
if(y>=cost[x]){
unused[S].push(P(cost[x]=y,x));
return;
}
best=cost[x]=y;
cnt[S]++;
for(i=1;i<8;i++){
y=getused(i);
if(!y)continue;
if(cost[y]<=best)continue;
cnt[mask[y]]--;
if(check())best=cost[y],who=y;
cnt[mask[y]]++;
}
if(who){
is[x]=1;
used[S].push(P(cost[x],x));
ans+=cost[x]-best;
cnt[mask[who]]--;
is[who]=0;
unused[mask[who]].push(P(cost[who],who));
}else{
cnt[S]--;
unused[S].push(P(cost[x],x));
}
}
}
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++){
char s[9];
scanf("%s%d",s,&cost[i]);
for(j=0;s[j];j++){
if(s[j]=='D')mask[i]|=1;
else if(s[j]=='S')mask[i]|=2;
else mask[i]|=4;
}
cnt[mask[i]]++;
}
for(i=0;i<3;i++)for(j=1;j<8;j++)if(j>>i&1)adj[i]|=1<<j;
adj[3]=adj[0]|adj[1];
num=n/4;
for(S=1;S<1<<4;S++){
int T=0,sum=0;
for(i=0;i<4;i++)if(S>>i&1)T|=adj[i];
for(i=1;i<8;i++)if(T>>i&1)sum+=cnt[i];
int pop=__builtin_popcount(S);
num=min(num,sum/pop);
bound[T]=max(bound[T],pop);
}
for(i=1;i<256;i++)if(bound[i]){
lim[++clim].mask=i;
lim[clim].cap=num*bound[i];
}
for(i=1;i<=n;i++)pool[i]=i;
sort(pool+1,pool+n+1,cmp);
for(i=n;i;i--){
x=pool[i];
cnt[mask[x]]--;
if(!check()){
ans+=cost[x];
is[x]=1;
cnt[mask[x]]++;
used[mask[x]].push(P(cost[x],x));
}else unused[mask[x]].push(P(cost[x],x));
}
scanf("%d",&q);
while(q--)scanf("%d%d",&x,&y),modify(x,y),printf("%lld\n",ans);
}
I. Guess Cycle Length
#include<bits/stdc++.h>
using namespace std;
constexpr int MAGIC_S=3333,MAGIC_B=3333;
int main()
{
ios_base::sync_with_stdio(false);
auto walk=[&](int x)
{
cout<<"walk "<<x<<endl;
int y;
cin>>y;
return y;
};
mt19937 rng(58);
int maxx=0;
for(int i=1;i<=MAGIC_S;i++)
{
int x=rng()%1000000001;
maxx=max(maxx,walk(x));
}
map<int,int> mp;
for(int i=MAGIC_B-1;i>=0;i--)
{
int x=walk(1);
if(mp.count(x))
{
cout<<"guess "<<mp[x]-i<<endl;
return 0;
}
mp[x]=i;
}
for(int i=0;i<MAGIC_B;i++)
{
int x;
if(i==0)x=maxx;
else x=MAGIC_B;
int y=walk(x);
if(mp.count(y))
{
cout<<"guess "<<maxx+i*MAGIC_B+mp[y]<<endl;
return 0;
}
}
assert(0);
return 0;
}
J. Painting
#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const int N=300005,K=19,inf=1000010;
int f[N][K],d[N];
set<P>T;
struct E{int k,b;}e[N];
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
struct Frac{
ll up,down;
Frac(){}
Frac(ll _up,ll _down){
up=_up,down=_down;
if(down<0)up*=-1,down*=-1;
}
void simplify(){
if(!up){down=1;return;}
ll t=gcd(up>0?up:-up,down);
up/=t,down/=t;
}
void show(){
simplify();
printf("%lld/%lld",up,down);
}
};
struct Point{
Frac x,y;
Point(){}
Point(Frac _x,Frac _y){x=_x,y=_y;}
void show(){
putchar('(');
x.show();
putchar(',');
y.show();
putchar(')');
}
}h[N];
inline Point intersection(const E&A,const E&B){
return Point(Frac(B.b-A.b,A.k-B.k),Frac(1LL*A.k*B.b-1LL*A.b*B.k,A.k-B.k));
//(v/v,v^2/v)
}
inline int sgn(const E&A,const Point&B){
Frac t(B.x.up*A.k+B.x.down*A.b,B.x.down);
//(v^2,v)
ll tmp=t.up*B.y.down-t.down*B.y.up;
//t.up/t.down-y.up/y.down
if(!tmp)return 0;
return tmp>0?1:-1;
//1 means line A is above point B
}
inline int lca(int x,int y){
if(d[x]<d[y])swap(x,y);
for(int i=K-1;~i;i--)if(d[f[x][i]]>=d[y])x=f[x][i];
if(x==y)return x;
for(int i=K-1;~i;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
return f[x][0];
}
inline int find(const E&e,int x,int top,int t){
for(int j=K-1;~j;j--){
int o=f[x][j];
if(d[o]<=d[top])continue;
if(sgn(e,h[o])*t>=0)x=o;
}
while(x!=top&&sgn(e,h[x])*t>=0)x=f[x][0];
if(x!=top&&sgn(e,h[x])*t<0)return x;
return 0;
}
int main(){
int n,W;
scanf("%d%d",&n,&W);
e[n+1].b=0;
h[n+1]=Point(Frac(1,1),Frac(0,1));
d[n+1]=1;
T.insert(P(0,n+1));
e[n+2].b=0;
h[n+2]=Point(Frac(1,1),Frac(inf,1));
d[n+2]=1;
T.insert(P(inf,n+2));
for(int i=1;i<=n;i++){
int A,B,C;
scanf("%d%d%d",&A,&B,&C);
e[i].k=B-A;
e[i].b=A;
set<P>::iterator it=T.lower_bound(P(A,0));
int nxt=it->second;
it--;
int pre=it->second;
if(C)T.insert(P(A,i));
int top=lca(pre,nxt);
int fa=find(e[i],pre,top,1);
if(!fa)fa=find(e[i],nxt,top,-1);
if(!fa)fa=top;
d[i]=d[fa]+1;
f[i][0]=fa;
if(!fa)h[i]=Point(Frac(1,1),Frac(B,1));
else{
h[i]=intersection(e[i],e[fa]);
if(C)for(int j=1;j<K;j++)f[i][j]=f[f[i][j-1]][j-1];
}
Point ans=h[i];
ans.x.up*=W;
ans.show();
puts("");
}
}
K. Master of Both
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1000050;
const int maxd=26;
int top=0;
int son[maxn+50][maxd];
int sz[maxn+50];
int val[maxn+50];
ll cnt[maxd+5][maxd+5];
ll ans2=0;
void ins(int x,const string &str,int pos,int len){
sz[x]++;
if (pos==len){
val[x]++;
ans2+=sz[x]-val[x];
return;
}
int now=str[pos]-'a';
for (int i=0;i<maxd;i++) if (i!=now && son[x][i]!=-1) cnt[now][i]+=sz[son[x][i]];
int& nxt=son[x][now];
if (nxt==-1) nxt=++top;
ins(nxt,str,pos+1,len);
}
int n,Q;
string str;
int main(){
ios_base::sync_with_stdio(false);
memset(son,-1,sizeof(son));
cin >> n >> Q;
for (int i=1;i<=n;i++){
cin >> str;
ins(0,str,0,str.length());
}
for (;Q--;){
cin >> str;
int len=str.length();
ll ans=ans2;
for (int i=0;i<len;i++)
for (int j=i+1;j<len;j++) ans+=cnt[str[i]-'a'][str[j]-'a'];
cout << ans << "\n";
}
return 0;
}
L. Levenshtein Distance
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=200010,K=35;
int k,n,m,cnt,i,j,x,y,z,Log[N<<1],f[K][K<<1],g[N],ans[K];
char a[N],b[N],s[N<<2];
namespace SA{
int n,rk[N<<2],sa[N<<2],h[N<<2],tmp[N<<2],cnt[N<<2],f[18][N<<1];
void suffixarray(int n,int m){
int i,j,k;n++;
for(i=0;i<n;i++)cnt[rk[i]=s[i]]++;
for(i=1;i<m;i++)cnt[i]+=cnt[i-1];
for(i=0;i<n;i++)sa[--cnt[rk[i]]]=i;
for(k=1;k<=n;k<<=1){
for(i=0;i<n;i++){
j=sa[i]-k;
if(j<0)j+=n;
tmp[cnt[rk[j]]++]=j;
}
sa[tmp[cnt[0]=0]]=j=0;
for(i=1;i<n;i++){
if(rk[tmp[i]]!=rk[tmp[i-1]]||rk[tmp[i]+k]!=rk[tmp[i-1]+k])cnt[++j]=i;
sa[tmp[i]]=j;
}
memcpy(rk,sa,n*sizeof(int));
memcpy(sa,tmp,n*sizeof(int));
if(j>=n-1)break;
}
n--;
for(j=rk[h[i=k=0]=0];i<n;i++,k++)
while(~k&&s[i]!=s[sa[j-1]+k])h[j]=k--,j=rk[sa[j]+1];
for(i=1;i<=n;i++)f[0][i]=h[i];
for(j=1;(1<<j)<=n;j++)for(i=1;i+(1<<j)-1<=n;i++)f[j][i]=min(f[j-1][i],f[j-1][i+(1<<(j-1))]);
}
inline int ask(int x,int y){
x=rk[x],y=rk[y];
if(x>y)swap(x,y);
int k=Log[y-x];
return min(f[k][x+1],f[k][y-(1<<k)+1]);
}
}
inline int lcp(int x,int y){
if(x>n||y>m)return 0;
return SA::ask(x-1,y+n);
}
inline void umax(int&a,int b){a<b?(a=b):0;}
inline void umin(int&a,int b){a>b?(a=b):0;}
int main(){
scanf("%d%s%s",&k,b+1,a+1);
n=strlen(a+1),m=strlen(b+1);
for(i=1;i<=n;i++)s[cnt++]=a[i];
s[cnt++]='#';
for(i=1;i<=m;i++)s[cnt++]=b[i];
for(i=2;i<=cnt;i++)Log[i]=Log[i>>1]+1;
SA::suffixarray(cnt,256);
for(i=1;i<=n;i++){
if(n-i+1<m-k)break;
for(j=m-k;j<=m+k;j++){
x=i+j-1;
if(x>=i&&x<=n)g[x]=N;
}
for(j=0;j<=k;j++)for(x=-k;x<=k;x++)f[j][x+K]=0;
f[0][K]=i;
for(j=0;j<=k;j++)for(x=-k;x<=k;x++){
y=f[j][x+K];
if(!y)continue;
z=y-i+x+1;
y+=lcp(y,z);
z=y-i+x+1;
if(z>m)umin(g[y-1],j);
if(j<k){
if(y<=n&&z<=m)umax(f[j+1][x+K],y+1);
if(y<=n)umax(f[j+1][x+K-1],y+1);
if(z<=m)umax(f[j+1][x+K+1],y);
}
}
for(j=m+k;j>=m-k;j--){
x=i+j-1;
if(x>=i&&x<=n){
if(x<n&&j<m+k)umin(g[x],g[x+1]+1);
if(g[x]<=k)ans[g[x]]++;
}
}
}
for(i=0;i<=k;i++)printf("%d\n",ans[i]);
}
M. Please Save Pigeland
#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using ll=long long;
const int N=5e5+1e3+7;
int n,k,c[N],key[N];
vector<pii>g[N];
struct Data{
ll a,g;
};
Data operator +(const Data &a,const Data &b)
{
if(b.a==-1)
return a;
if(a.a==-1)
return b;
return {a.a,__gcd(__gcd(a.g,b.g),abs(a.a-b.a))};
}
Data operator +(const Data &a,ll b)
{
if(a.a==-1)
return a;
return {a.a+b,a.g};
}
int sz[N];
ll d[N];
Data f[N];
void dfs(int x,int F)
{
f[x].a=-1;
sz[x]=key[x];
for(auto [v,w]:g[x])
{
if(v==F)
continue;
dfs(v,x);
d[x]+=d[v]+1ll*w*sz[v];
sz[x]+=sz[v];
f[x]=f[x]+(f[v]+w);
}
if(key[x])
f[x]=f[x]+Data({0,0});
}
ll ans;
void go(int x,int F,Data G,ll D)
{
Data tG=G+f[x];
ll tD=D+d[x];
ll rG=__gcd(tG.a,tG.g);
if(rG)
ans=min(ans,tD/rG);
else
ans=min(ans,tD);
// cout<<x<<" "<<tD<<endl;
vector<Data>pf,sf;
pf.push_back({-1,0});
for(int i=0;i<g[x].size();i++)
{
auto [v,w]=g[x][i];
if(v==F)
continue;
pf.push_back(pf.back()+(f[v]+w));
}
sf.resize(pf.size()+1);
sf.back()={-1,0};
int t=(int)sf.size()-2;
for(int i=(int)g[x].size()-1;i>=0;i--)
{
auto [v,w]=g[x][i];
if(v==F)
continue;
sf[t]=sf[t+1]+(f[v]+w);
t--;
}
t=0;
for(int i=0;i<g[x].size();i++)
{
auto [v,w]=g[x][i];
if(v==F)
continue;
++t;
ll nD=D+d[x]-d[v]-1ll*sz[v]*w+1ll*(k-sz[v])*w;
Data nG=(pf[t-1]+sf[t+1]+G)+w;
if(key[x])
nG=(nG+Data{w,0});
go(v,x,nG,nD);
}
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=k;i++)
scanf("%d",&c[i]),key[c[i]]=1;
for(int i=1;i<n;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
g[u].push_back({v,w});
g[v].push_back({u,w});
}
ans=3e18;
dfs(1,0);
go(1,0,{-1,0},0);
printf("%lld\n",ans*2);
}
/*
5 3
3 4 5
1 2 2
2 3 4
2 5 4
3 4 6
*/
- Programming Hangzhou Regional Contest 2022programming hangzhou regional contest hangzhou regional contest 2022 hangzhou regional contest 2023 programming字典hangzhou regional programming shenyang regional contest programming regional contest 2023 programming regional yinchuan contest programming regional contest aefhkl intercollegiate programming regional contest regional contest nanjing 2022