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.在做题过程中可以去模拟样例，模拟算法过程，从具体实现中找条件
标签：head,颜色,int,20230318,tot,edge,maxn,jnxxhzz,模拟 From： https://www.cnblogs.com/hewanying0622/p/17299550.html