test25
一本通tour
把边当作点，连像传递奖牌的另一个点，每一个奖牌经过一条树上到根的链，直接深搜+set 即可查询出在谁那里呆的最久。
#include<bits/stdc++.h>
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define pb push_backusing namespace std;const int N=200005;int n, m, x[N], y[N], lst[N], fa[N], val[N], Ans[N];
vector<int> to[N];
struct node {int u, cnt;bool operator<(const node &rhs) const {if(cnt!=rhs.cnt) return cnt>rhs.cnt;return u<rhs.u; }
};
multiset<node> qwq;void dfs(int x) {int i=y[x];qwq.erase((node){i,val[i]});val[i]+=(fa[x]?fa[x]:m+1)-x;qwq.insert((node){i,val[i]});++Ans[(*qwq.begin()).u];for(int y:to[x]) dfs(y);qwq.erase((node){i,val[i]});val[i]-=(fa[x]?fa[x]:m+1)-x;qwq.insert((node){i,val[i]});
}signed main() {freopen("ybt.in","r",stdin); freopen("ybt.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> n >> m;up(i,1,m) cin >> y[i] >> x[i], ++x[i], ++y[i];dn(i,m,1) {if(lst[y[i]]) {fa[i]=lst[y[i]];to[lst[y[i]]].pb(i);}lst[x[i]]=i;}up(i,1,n) qwq.insert((node){i,0});up(i,1,m) if(!fa[i]) qwq.clear(), dfs(i);up(i,1,n) cout << Ans[i] << ' ';return 0;
}
洛谷luogu
没有奇环就是二分图，但是带着二分属性不好做。不妨考虑随机染色然后暴力 dp，正确的概率大于 \(\frac{1}{2^9}\)，不妨认为随机 \(2^{k-1}\) 正确的概率是 \(\frac{1}{2}\)，那么随机 \(2^{k-1}\times 30\) 次错误率不超过 \(\frac{1}{2^{30}}\)。
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define min(a,b) ((a)<(b)?(a):(b))
#define pb push_backusing namespace std;const int N=85, M=15, inf=1e18;int n, k, dis[N][N], Ans=inf, gp[N], f[M][N];signed main() {freopen("luogu.in","r",stdin); freopen("luogu.out","w",stdout);mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());chrono::steady_clock::now().time_since_epoch().count();ios::sync_with_stdio(0);cin.tie(0);cin >> n >> k;up(i,1,n) up(j,1,n) cin >> dis[i][j];int T=37*(1<<(k-1));up(t,1,T) {up(i,2,n) gp[i]=rd()&1;up(i,2,n) f[0][i]=inf;up(u,1,k) {up(i,1,n) if(gp[i]==(u&1)) {f[u][i]=inf;up(j,1,n) if(gp[j]!=(u&1)) {f[u][i]=min(f[u][i],f[u-1][j]+dis[j][i]);}}}Ans=min(Ans,f[k][1]);}cout << Ans << '\n';return 0;
}
2023年的NOIselfEval
弹飞绵羊来的，考虑分块，维护每个点跳出本块之后会到哪、要几步。这样子更新和查询都是 \(O(\sqrt n)\) 的了，而且常数很小。
#include<bits/stdc++.h>
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)using namespace std;const int N=200005;int n, m, B, val[N], to[N], run[N];void build(int l,int r) {dn(i,r,l) {if(i+val[i]>r) to[i]=-1, run[i]=1;else to[i]=to[i+val[i]], run[i]=run[i+val[i]]+1;}
}signed main() {
// freopen("1.txt","r",stdin);freopen("selfeval.in","r",stdin); freopen("selfeval.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> n, B=sqrt(n);up(i,0,n-1) cin >> val[i];up(u,0,(n-1)/B) build(B*u,min(B*(u+1)-1,n-1));cin >> m;while(m--) {int opt, i, v=0;cin >> opt >> i;if(opt==1) {for( ; i<n; ) {if(to[i]==-1) i=i+val[i], ++v;else v+=run[i], i=to[i];}cout << v << '\n';}else {cin >> v, val[i]=v;build(B*(i/B),min(B*((i/B)+1)-1,n-1));}}return 0;
}
如果你能去 IOI CMS
先考虑一下题目求的是啥，切成 \(k+1\) 棵树求直径和，也就是选择恰好 \(k+1\) 条不相交的路径问权值和最大是多少咯。考虑 \(k+1=1\to n\) 的过程，先可以且更多的树拿更多的路径，然后会被迫去切开拿来贡献的边，直接上 wqs 二分，其实凸性不轻易严谨证明、但是单调性可以。
之后问题变成了取一条链会额外花费 \(\Delta\)，问选若干条链贡献和最大是多少。考虑怎么描述状态，考虑 \(f_{x,0/1}\) 表示子树到根向上传递和子树不向上传递的答案，转移是容易的。
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define pii pair<int,int>
#define pb push_back
#define mp make_pairusing namespace std;inline int read() {int X=0; bool flag=1; char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}if(flag) return X;return ~(X-1);
}const int N=300005;int n, k, Pluto;
vector<pii> to[N];struct data {int val, cnt;bool operator<(const data &rhs) const { return val==rhs.val?cnt>rhs.cnt:val<rhs.val; }
} f[N][3], nul, tmp;data operator+(data x,data y) { return (data){x.val+y.val,x.cnt+y.cnt}; }
data operator+(data x,int num) { return (data){x.val+num,x.cnt}; }
inline void chkmax(data &x,data y) { if(x<y) x=y; }
inline data max(data x,data y) { return x<y?y:x; }void dp(int x,int fad) {f[x][0]=f[x][1]=f[x][2]=nul;chkmax(f[x][2],tmp);for(pii p:to[x]) if(p.first!=fad) {int y=p.first, w=p.second;dp(y,x);chkmax(f[x][2],max(f[x][2]+f[y][0],f[x][1]+f[y][1]+w+tmp));chkmax(f[x][1],max(f[x][1]+f[y][0],f[x][0]+f[y][1]+w));chkmax(f[x][0],f[x][0]+f[y][0]);}chkmax(f[x][0],f[x][1]+tmp), chkmax(f[x][0],f[x][2]);
}void check(int mid) {tmp=(data){-mid,1}, dp(1,0);Pluto=f[1][0].cnt;
}signed main() {freopen("cms.in","r",stdin); freopen("cms.out","w",stdout);n=read(), k=read()+1;up(i,2,n) {int u=read(), v=read(), w=read();to[u].pb(mp(v,w));to[v].pb(mp(u,w));}int l=-1e12, r=1e12;while(l<r) {int mid=(l+r)>>1;check(mid);if(Pluto==k) {cout << f[1][0].val+mid*k << '\n';return 0;}if(Pluto>k) l=mid+1;else r=mid;}check(l), cout << f[1][0].val+l*k << '\n';return 0;
}