慢慢练习一些树的思维题 大部分是补的 留给自己复习
A Problem - 1324F - Codeforces
题意： 选择一些连通子树 让白子-黑子 的数量最大化
思路： 上下两遍扫描 处理出子树的最大值 然后再处理往上的最大值
#include<bits/stdc++.h> #define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typedef long long ll; const ll MAXN = 3e5+7; const ll mod =1e9+7; const ll inf =0x3f3f3f3f; const ll INF =0x3f3f3f3f3f3f3f3f; //如果 cnt1>cnt2 就加上子树的贡献 int dp[MAXN]; //dp[i]表示以i为根的树 可以存在的最大值 //转移方程 ： 向下：如果子节点的>0 就加上 // 向上： 如果父节点的子节点>0 就取最大值 否则取加上和不加上的最大值 vector<int> adj[MAXN]; void dfs_down(int u,int fa){ for(auto v:adj[u]){ if(v==fa)continue; dfs_down(v,u); if(dp[v]>0) dp[u]+=dp[v]; } } void dfs_up(int u,int fa){ for(auto v:adj[u]){ if(v==fa) continue; if(dp[v]>0) dp[v]=max(dp[u],dp[v]); else dp[v]=max(dp[v],dp[u]+dp[v]); dfs_up(v,u); } } void solve(){ int n;cin>>n; for(int i=1;i<=n;i++) { int a;cin>>a; if(a==0) dp[i]=-1; else dp[i]=1; } for(int i=1;i<n;i++){ int u,v;cin>>u>>v; adj[u].push_back(v); adj[v].push_back(u); } dfs_down(1,-1); dfs_up(1,-1); for(int i=1;i<=n;i++) cout<<dp[i]<<" "; } int main(){ solve(); }
题意： 这题与A比较相似 但是是处理删除后的最大值并且使删除的操作数量更少 难度更大一点
思路：dp[i][1]为以i为根节点的子树中 删除最少的点能达到的最大值
dp[i][0]为最小步数
只进行一次搜索就可以完成
如果>0 肯定要加上 <0 肯定要切割
如果等于0 已经操作次>1 就删掉 这样赚 否则加上
最后的时候 因为建树的时候是以1为节点 如果以其他为节点的时候 还要多删一下 因此操作数+1
#include<bits/stdc++.h> #define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typedef long long ll; const ll MAXN = 4e5+7; const ll mod =1e9+7; const ll inf =0x3f3f3f3f; const ll INF =0x3f3f3f3f3f3f3f3f; #define int long long vector<int > adj[MAXN]; int dp[MAXN][2];//dp[i][0]表示 包含i的i子树 操作次数 dp[i][1]表示操作后的最大权值和 int a[MAXN]; void dfs(int u,int fa){ dp[u][0]=0,dp[u][1]=a[u]; for(auto &v:adj[u]){ if(v==fa) continue; dfs(v,u); if(dp[v][1]<0){ dp[u][0]+=1; } else if(dp[v][1]>0){ dp[u][0]+=dp[v][0]; dp[u][1]+=dp[v][1]; } else{//=0的情况 如果v的操作数>1 删掉 否则加上去 if(dp[v][0]>=1){ dp[u][0]+=1; } else{ dp[u][0]+=dp[v][0]; dp[u][1]+=dp[v][1]; } } } // if(adj[u].size()==1) } void solve(){ int n;cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<n;i++){ int u,v;cin>>u>>v; adj[u].push_back(v); adj[v].push_back(u); } dfs(1,-1); int maxs=dp[1][1],maxt=dp[1][0]; for(int i=2;i<=n;i++){ if(dp[i][1]>maxs||(dp[i][1]==maxs&&dp[i][0]+1<maxt)){//更新最小操作数和最大权值和 maxs=dp[i][1]; maxt=dp[i][0]+1; } } // for(int i=1;i<=n;i++){ // cout<<"# "<<i<<" : "<<" t:"<<dp[i][0]<<" x:"<<dp[i][1]<<"\n"; // } // if(maxs==dp[1][1]&&maxt==dp[1][0]){//如果不是在1这个点取到的 操作数+1 cout<<maxs<<" "<<maxt; // } // else cout<<maxs<<" "<<maxt+1; } signed main(){ solve(); }
题意：最多可使用一次传送门 算出最短距离
思路：赛场上是把所有点搞到一起 然后用lca算距离 一直re 赛后学长提醒才发现树有环了 寄
不过想想这道题还是比较简单的 两个点相通有两个方法 1使用传送门 2不使用传送门
使用的情况 算出每个点到传送点的最大距离 然后距离相加 （或者建虚点 dij也行
不使用的情况 直接d[u]+d[v]-d[lca(u,v)] 取最小即可
#include<bits/stdc++.h> #define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typedef long long ll; const ll MAXN = 2e5+7; const ll mod =1e9+7; const ll inf =0x3f3f3f3f; const ll INF =0x3f3f3f3f3f3f3f3f; #define int long long int vis[MAXN],f[MAXN]; vector<pair<int,ll> > adj[MAXN]; int par[MAXN][20],dep[MAXN];ll dis[MAXN],d[MAXN]; void dfs(int u,int fa){ dep[u]=dep[fa]+1; par[u][0]=fa; for(int i=1;i<20;++i){ par[u][i]=par[par[u][i-1]][i-1]; } for(auto &i:adj[u]){ int v=i.first; if(v==fa) continue; dfs(v,u); } } int getLCA(int u,int v){ if(dep[u]<dep[v]) swap(u,v); for(int i=19;i>=0;--i){ if(dep[par[u][i]]>=dep[v]) u=par[u][i]; } if(u==v) return u; for(int i=19;i>=0;i--){ if(par[u][i]!=par[v][i]){ u=par[u][i]; v=par[v][i]; } } return par[u][0]; } void dfs_down(int u,int fa){ for(auto &i:adj[u]){ int v=i.first,w=i.second; if(v==fa) continue; dfs_down(v,u); //if(f[v]) dis[u]=0; dis[u]=min(dis[u],dis[v]+w); } } void dfs_up(int u,int fa){ for(auto &i:adj[u]){ int v=i.first,w=i.second; if(v==fa) continue; // if(f[u]) dis[v]=0; dis[v]=min(dis[v],dis[u]+w); dfs_up(v,u); } } void dfs_sum(int u,int fa){ for(auto &i:adj[u]){ int v=i.first,w=i.second; if(v==fa) continue; d[v]=d[u]+w; dfs_sum(v,u); } } void solve(){ int m,n;cin>>n>>m; int root; memset(dis,0x3f3f3f3f,sizeof(dis)); memset(d,0x3f3f3f3f,sizeof(d)); for(int i=0;i<m;i++){ int a;cin>>a; f[a]=1; if(i==0) root=a; dis[a]=0; } for(int i=1;i<n;i++){ int u,v,w;cin>>u>>v>>w; adj[u].push_back({v,w}); adj[v].push_back({u,w}); } d[root]=0; dfs_sum(root,-1); dfs(root,-1); dfs_down(root,-1); dfs_up(root,-1); int q;cin>>q; while(q--){ int u,v;cin>>u>>v; int ans=d[u]+d[v]-2*d[getLCA(u,v)]; ans=min(ans,dis[u]+dis[v]); cout<<ans<<"\n"; } } signed main(){ close; solve(); }
D Problem - 1363C - Codeforces
题意：每人轮流取一个点 谁先取到x谁输
思路：如果只有一个点 先手输 如果两个点 后手输 剩下判断奇偶性即可
#include<bits/stdc++.h> #define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typedef long long ll; const ll MAXN = 3e5+7; const ll mod =1e9+7; const ll inf =0x3f3f3f3f; const ll INF =0x3f3f3f3f3f3f3f3f; vector<int> adj[MAXN]; int IN[MAXN]; int size[MAXN]; void dfs(int u,int fa){ size[u]=1; for(auto v:adj[u]){ if(v==fa) continue; size[u]+=size[v]; } } void solve(){ int n,x;cin>>n>>x; for(int i=1;i<=n;i++) size[i]=0,IN[i]=0; for(int i=1;i<n;i++){ int u,v;cin>>u>>v; adj[u].push_back(v); adj[v].push_back(u); IN[u]++; IN[v]++; } if(IN[x]==1||IN[x]==0){ cout<<"Ayush"<<"\n"; return; } // dfs(1,-1); int maxs=0; if(n%2==0){ cout<<"Ayush\n"; } else cout<<"Ashish\n"; } int main(){ int t;cin>>t; while(t--) solve(); }
E Problem - 1404B - Codeforces
题意：A和B各在一个点上 分别一步可以走da与db A先走 如果A能追上B A胜 否则B
思路：首先如果B在A的一次控制范围 即d(a,b)<=da A必胜
如果da*2>=树的直径 那么只要A站直径中间 B逃不走
如果da*2>=db da可以慢慢逼近db //这里还不会证明
写起来简单