T1.彩虹树
对于每一个u，v，我们都要去算u->v路径上有多少个不同的元素
很显然，<span class="cke_reset cke_widget_drag_handler_container"><img src="data:image/gif;base64,R0lGODlhAQABAPABAP///wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==" width="15" height="15" class="cke_reset cke_widget_drag_handler" title="点击并拖拽以移动" data-cke-widget-drag-handler="1" data-mce-src="data:image/gif;base64,R0lGODlhAQABAPABAP///wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw=="><span class="cke_image_resizer" title="点击并拖拽以改变尺寸"><span class="cke_widget_edit_container" title="编辑图片">编辑每一个去枚举是不现实的
所以我们要考虑换个方法枚举
既然是要求每条路径上不同颜色的数量
我们可以考虑枚举每一个颜色在多少条路径上出现过
考虑每一种颜色，我们把那种颜色的点在树上删掉
那么就会形成若干个块，我们把这些块相乘
这样的思路是有关正着算，是一个一个往上加的
我们还可以倒着来想，考虑在那些方案中是没有这个颜色的
对于每个节点v，它子树中的节点连出去一定会经过这个颜色
那在与v颜色相同的上一个节点间，这些节点两两相连是不会经过col[v]的，是被减去的
这样就可以用一个dfs来计算每次减少的数量
时间复杂度为O(n)
代码
#include <bits/stdc++.h> using namespace std; #define ll long long const int maxn=2e5+10; int n,col[maxn],head[maxn],tot=0; ll sum[maxn],ans=0,cnt=0,sz[maxn]; bool vis[maxn]; struct edge{ int v,nxt; }e[maxn*2]; void add(int u,int v){ e[++tot]=(edge){v,head[u]}; head[u]=tot; e[++tot]=(edge){u,head[v]}; head[v]=tot; } void init(){ for(int i=1;i<=n;i++) vis[i]=false,col[i]=sz[i]=head[i]=sum[i]=0; tot=ans=cnt=0; } void dfs(int u,int fa){ sz[u]=1;//sum[col[u]]指枚举到此时，树中以col[u]这一颜色的节点为根的节点数量 ll pre=sum[col[u]],c=0,tmp=0,szv; for(int i=head[u];i;i=e[i].nxt){ int v=e[i].v; if(v==fa) continue; dfs(v,u); sz[u]+=sz[v]; tmp=sum[col[u]]-pre;//计算以v为根的子树中，以col[u]颜色为根的子树的数量 szv=sz[v]-tmp;//以v为根的子树中，互相连通且不经过col[u]颜色的点的数量 pre=sum[col[u]];//记得更新pre ans-=1ll*szv*(szv-1)/2; c+=tmp;//去重，防止每次更新sum是都要多加tmp } sum[col[u]]+=sz[u]-c; } int main(){ scanf("%d",&n); init(); for(int i=1;i<=n;i++){ scanf("%d",&col[i]); if(!vis[col[i]]) vis[col[i]]=true,cnt++; } for(int i=1;i<n;i++){ int u,v; scanf("%d%d",&u,&v); add(u,v); } ans=1ll*cnt*n*(n-1)/2;//每条路径都会经过所有颜色的总数 dfs(1,0); for(int i=1;i<=n;i++){ if(!sum[i]) continue; ll tmp=n-sum[i]; ans-=1ll*tmp*(tmp-1)/2; }//最后在进行一次整棵树的去重 printf("%lld\n",ans); return 0; }
T2.最小生成树
给定了生成树，可以去模拟最小生成树的过程
为什么要选这条边？
因为它在连通u,v两点中w最小
我们令给定生成树上的边叫树边，那么其他的边都是非树边
对于每条非树边，我们要让树上它所连接的两点上的路径最大值小于等于非树边的值
这样这条非树边才不会被选
然而我们可以先把非树边从小到大排序，那么对于每一条树边，就只会进行一次修改
这样就可以边缩点边修改，节约时间
时间复杂度O(mlogm)
代码
#include <bits/stdc++.h> using namespace std; #define ll long long const int maxn=1e5+10; int n,m,cnt=0,head[maxn],tot=0; ll ans=0; map<pair<int,int>,int> mp; struct edge{ int u,v,val,nxt; bool operator < (const edge &rhs) const{ return val<rhs.val; } }e[maxn],t[maxn]; struct node{ int fa,val,dep; void mmset(int w){//每一次更新答案 if(w<val) ans+=1ll*(val-w); val=w; } }a[maxn]; void add(edge p){//对树边进行建树 int u=p.u,v=p.v,val=p.val; t[++tot]=(edge){u,v,val,head[u]}; head[u]=tot; t[++tot]=(edge){v,u,val,head[v]}; head[v]=tot; } void dfs(int u,int fa){//dfs生成树 a[u].fa=fa;a[u].dep=a[fa].dep+1; for(int i=head[u];i;i=t[i].nxt){ int v=t[i].v,val=t[i].val; if(v==fa) continue; a[v].val=val; dfs(v,u); } } int getans(int u,int v,int w){//每一条非树边分别对树边进行优化 if(u==v) return u; int p=0; if(a[u].dep==a[v].dep){ a[u].mmset(w); a[v].mmset(w); p=getans(a[u].fa,a[v].fa,w); } if(a[u].dep>a[v].dep){ a[u].mmset(w); p=getans(a[u].fa,v,w); } if(a[u].dep<a[v].dep){ a[v].mmset(w); p=getans(u,a[v].fa,w); } if(u!=p) a[u].fa=p; if(v!=p) a[v].fa=p;//缩点 return p; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].val); if(e[i].u>e[i].v) swap(e[i].u,e[i].v); mp.insert(make_pair(make_pair(e[i].u,e[i].v),i)); } for(int i=1,u,v;i<n;i++){ scanf("%d%d",&u,&v); cnt=mp[make_pair(u,v)]; mp[make_pair(u,v)]=-1; add(e[cnt]);//建树 } dfs(1,0); sort(e+1,e+m+1); for(int i=1;i<=m;i++){ if(mp[make_pair(e[i].u,e[i].v)]==-1) continue; getans(e[i].u,e[i].v,e[i].val); } printf("%lld\n",ans); return 0; }
T3.快速排序
略
总结
1.从多角度分析问题，如T1中每条路径的颜色可以转换成每个颜色所在的路径数量
然而有可以反向操作，算出最大方案数再减去不合理的，是常见的思路
2.在做题过程中可以去模拟样例，模拟算法过程，从具体实现中找条件