[JLOI2014]松鼠的新家

树上差分常见套路：子树和为原数组

苦逼菜鸡72行打错qwq 因为只有第一个点val不用-1，后面访问到的都要-1（对于一条路径起点权值不用加）

#include<bits/stdc++.h> using namespace std; #define in Read() int in{ int i=0;bool f=true;char ch=0; while(!isdigit(ch)&&ch!='-') ch=getchar(); if(ch=='-') ch=getchar(),f^=1; while(isdigit(ch)) i=(i<<1)+(i<<3)+ch-48,ch=getchar(); return f?i:-i; } const int N=3e5+5; int n,a[N],val[N]; int f[N][25],dep[N]; vector<int>G[N]; void DFS(int u,int fa){ f[u][0]=fa; dep[u]=dep[fa]+1; for(int v:G[u]){ if(v==fa) continue; DFS(v,u); } return; } void get(int u,int fa){ for(int v:G[u]){ if(v==fa) continue; get(v,u); val[u]+=val[v]; } return; } int lca(int u,int v){ if(dep[u]<dep[v]) swap(u,v); for(int l=20;l>=0;--l) if(dep[f[u][l]]>=dep[v]) u=f[u][l]; if(u==v) return u; for(int l=20;l>=0;--l) if(f[u][l]!=f[v][l]) u=f[u][l],v=f[v][l]; return f[u][0]; } int main(){ // freopen("1.in","r",stdin); // freopen("my.out","w",stdout); n=in; for(int i=1;i<=n;++i) a[i]=in; for(int i=1;i<n;++i){ int u=in,v=in; G[u].push_back(v); G[v].push_back(u); } DFS(1,0); for(int l=1;l<=20;++l) for(int u=1;u<=n;++u) f[u][l]=f[f[u][l-1]][l-1]; for(int i=1;i<n;++i){ int u=a[i],v=a[i+1],s=lca(u,v); ++val[u]; ++val[v]; --val[s]; --val[f[s][0]]; } get(1,0); for(int i=2;i<=n;++i) --val[a[i]]; for(int i=1;i<=n;++i) printf("%d\n",val[i]); return 0; }

NOIP2015 运输计划

一看又是一道树剖题

下放边权lca的下放边权不做贡献找$(\sum cnt\times time)-ma{x}_{cnt\times time}$，边加边记

要求的不是总时间，是最长时间，就是最小化路径的最长时间 又读错题

考虑二分答案 对于长度大于mid的，扔树上差分 如果找到一条边边权>=最长路径-mid，则mid合法

真TM什么都设得出来 13行,f[N][0],val[N],

#include<bits/stdc++.h> using namespace std; #define in Read() int in{ int i=0;bool f=true;char ch=0; while(!isdigit(ch)&&ch!='-') ch=getchar(); if(ch=='-') ch=getchar(),f^=1; while(isdigit(ch)) i=(i<<1)+(i<<3)+ch-48,ch=getchar(); return f?i:-i; } const int N=3e5+5; int n,m,dep[N],f[N][25],val[N],dif[N],dis[N],max_dis,max_wei; int tot,first[N],nxt[N<<1],wei[N<<1],aim[N<<1]; struct Query{ int u,v,dis,lca; }q[N]; void ljb(int u,int v,int w){ ++tot; nxt[tot]=first[u]; first[u]=tot; wei[tot]=w; aim[tot]=v; return; } void DFS(int u,int fa){ dep[u]=dep[fa]+1; f[u][0]=fa; for(int e=first[u];e;e=nxt[e]){ int v=aim[e]; if(v==fa) continue; val[v]=wei[e]; dis[v]=dis[u]+wei[e]; DFS(v,u); } return; } int lca(int u,int v){ if(dep[u]<dep[v]) swap(u,v); for(int l=20;l>=0;--l) if(dep[f[u][l]]>=dep[v]) u=f[u][l]; if(u==v) return u; for(int l=20;l>=0;--l) if(f[u][l]!=f[v][l]) u=f[u][l],v=f[v][l]; return f[u][0]; } void get(int u,int fa){ for(int e=first[u];e;e=nxt[e]){ int v=aim[e]; if(v==fa) continue; get(v,u); dif[u]+=dif[v]; } return; } bool check(int mid){ memset(dif,0,sizeof dif); int cnt=0;max_wei=0; for(int i=1;i<=m;++i) if(q[i].dis>mid){ int u=q[i].u,v=q[i].v,s=q[i].lca; ++dif[u]; ++dif[v]; --dif[s]; --dif[s]; ++cnt; } get(1,0); for(int i=1;i<=n;++i) if(dif[i]==cnt&&max_wei<val[i]) max_wei=val[i]; return max_wei>=max_dis-mid; } int get_ans(int l,int r){ int ans; while(l<=r){ int mid=l+r>>1; if(check(mid)) r=mid-1,ans=mid; else l=mid+1; } return ans; } int main(){ n=in,m=in; for(int i=1;i<n;++i){ int u=in,v=in,w=in; ljb(u,v,w); ljb(v,u,w); max_wei=max(max_wei,w); } DFS(1,0); // for(int s=1;s<=n;++s) printf("%d ",f[s][0]);puts(""); for(int l=1;l<=20;++l) for(int u=1;u<=n;++u) f[u][l]=f[f[u][l-1]][l-1]; // for(int i=1;i<=n;++i){ // printf("%d: ",i); // for(int j=0;j<=5;++j) printf("%d ",f[i][j]); // puts(""); // } // printf("%d\n",lca(4,5)); // return 0; for(int i=1;i<=m;++i){ q[i].u=in,q[i].v=in; q[i].lca=lca(q[i].u,q[i].v); q[i].dis=dis[q[i].u]+dis[q[i].v]-(dis[q[i].lca]<<1); max_dis=max(max_dis,q[i].dis); } printf("%d\n",get_ans(max_dis-max_wei,max_dis)); return 0; }

还有一个T3 NOIP2015 天天爱跑步 不过不太想写 用线段树合并写多好