特教的理性愉悦(ecstasy)
【分析】
来二中的又一道图论题,貌似还是2016noi导刊的一套题。。。
从题面开始分析,这明显是一道图论题,而且还是一道LCA的题目,或者是和LCA有关的一道题。但在询问过程中两个点之间未必联通,貌似无法直接用LCA算法求出(u,v)的路径。仔细思考树的一些特性我们会发现,如果在不走回头路的情形下,树中两点之间的路径唯一的。换言之如果(u,v)联通,那么当前两点间的路径和建树完全后两点间的距离是一样的。
具体上,我们先将所有所有操作存起来,建成一棵树并完成LCA的预处理(本题使用的是简单直观的倍增算法)。然后我们重新枚举操作,并用并查集维护操作1和判断(u,v)是否在同一棵树中(也就是同一个集合)。碰到操作2,如果不在同一集合就直接输出-1;否则找到(u,v)的LCA,沿着路径走一遍就能得到正解。(这里有一个规律可以推导,距离和=sigma(n+1-i)*i*wi,n为路径中边的总数,wi为每条边的权值)
单次操作在最坏情形下的时间复杂度为O(n),总的复杂度为O(n*m)。也就是50分的做法。
这里面的m是不能再减小了,只能从n处入手,改变直接枚举整条路径这种方式来换取更小的时间复杂度。比较容易想到的是利用预处理和前缀和来优化时间。我的思路从这里无法再延伸了,最终还是只能在考场上敲出五十分的解法(其中还因为忘记开longlong而WA了两个点)。考后试题讲解中一位大佬的算法给了我很多启迪:他是这样说的,我们虽然无法直接用简单的一位前缀和求出路径的权值,但我们能动用一些数学方法,预处理出高阶前缀,通过一些神奇的运算在O(1)的时间内算出答案。
观察原来那个sigma式子,我们发现从u或v任意一端枚举所得的结果是不变的。我们可以分别求出从u到LCA的权值和从v到LCA的权值。仔细观察可以发现,两个因数的大小都与深度有关。
盗用一下某位博主的一张图(这里边6-7的系数标错了应该是6*2):
(如果这篇blog看不懂也可光临一下他的博客,逃)
其中一个数随点深度的增加而递减。用ndis表示从深度的负数乘上边的权值(这里边的权值可以下沉到它下端的点上,方便计算)。为了防止溢出我们改为总数n减去深度再乘上他的边权(或者是点权?,雾),接下来计算的操作中你将会看到n被完全消掉。
我们先用ndis[x]-ndis[lca]发现求到的全是负数,而且貌似递减的顺序不太对(雾)。别担心这时候应该再减去(n-dep[x])*(dis[lca]-dis[x])。我们惊异的发现不仅原来的n被全消掉了,而且变成了一个从x出发的系数成等差序列递增的值的和。同理我们也可以求出y的部分。
五十分代码如下:
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+1000;
const int M=3e5;
int f[N];
struct Opt{
int x,y,w,k;
}opt[M];
struct Edge{
int v,c,nxt;
}edge[N<<1];
int head[N],tot=0;
int n,m,large,s=1;
int d[N],p[N][20],val[N];
void add_edge(int x,int y,int c){
edge[tot].v=y;
edge[tot].c=c;
edge[tot].nxt=head[x];
head[x]=tot++;
return ;
}
void dfs(int u,int dep){
d[u]=dep;
for(int i=head[u];i!=-1;i=edge[i].nxt){
int v=edge[i].v;
if(!d[v]){
p[v][0]=u;
val[v]=edge[i].c;
dfs(v,dep+1);
}
}
}
void init_lca(){
dfs(s,1);
p[s][0]=s;
large=0;
while(1<<large<=n)large++;
large--;
for(int j=1;j<=large;j++)
for(int i=1;i<=n;i++)
p[i][j]=p[p[i][j-1]][j-1];
return ;
}
int find(int x){
if(f[x]!=x) f[x]=find(f[x]);
return f[x];
}
int lca(int x,int y,int& dist){
dist=0;
if(d[x]>d[y])swap(x,y);
for(int i=large;i>=0;i--)
if(d[y]-d[x]>=1<<i) y=p[y][i],dist+=1<<i;
if(x==y) return x;
for(int i=large;i>=0;i--)
if(p[x][i]!=p[y][i]){
x=p[x][i];
y=p[y][i];
dist+=1<<i+1;
}
dist+=2;
return p[x][0];
}
int main(){
freopen("ecstasy.in","r",stdin);
freopen("ecstasy.out","w",stdout);
memset(head,-1,sizeof(head));
cin>>n>>m;
for(int i=1;i<=m;i++){
int d;
scanf("%d",&d);
if(d==1){
opt[i].k=d;
scanf("%d%d%d",&opt[i].x,&opt[i].y,&opt[i].w);
add_edge(opt[i].x,opt[i].y,opt[i].w);
add_edge(opt[i].y,opt[i].x,opt[i].w);
}
else{
opt[i].k=d;
scanf("%d%d",&opt[i].x,&opt[i].y);
}
}
init_lca();
for(int i=1;i<=n;i++)
f[i]=i;
for(int i=1;i<=m;i++){
if(opt[i].k==1){
f[find(opt[i].x)]=find(opt[i].y);
}
else{
if(find(opt[i].x)!=find(opt[i].y)){
printf("-1\n");
continue;
}
else{
long long dist,x=opt[i].x,y=opt[i].y,k,ans=0;
int LCA=lca(x,y,dist);
k=1;
while(x!=LCA){
ans+=val[x]*(dist+1-k)*k;
k++,x=p[x][0];
}
k=1;
while(y!=LCA){
ans+=val[y]*(dist+1-k)*k;
k++,y=p[y][0];
}
printf("%lld\n",ans);
}
}
}
return 0;
}
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+1000;
const int M=3e5;
int f[N];
struct Opt{
int x,y,w,k;
}opt[M];
struct Edge{
int v,c,nxt;
}edge[N<<1];
int head[N],tot=0;
int n,m,large,s=1;
long long d[N],p[N][20],val[N];
long long dis[N],ndis[N],n2dis[N];
void add_edge(int x,int y,int c){
edge[tot].v=y;
edge[tot].c=c;
edge[tot].nxt=head[x];
head[x]=tot++;
return ;
}
void dfs(int u,int dep){
d[u]=dep;
for(int i=head[u];i!=-1;i=edge[i].nxt){
int v=edge[i].v;
if(!d[v]){
p[v][0]=u;
val[v]=edge[i].c;
dis[v]=dis[u]+edge[i].c;
ndis[v]=ndis[u]+(n-d[u])*edge[i].c;
n2dis[v]=n2dis[u]+(n-d[u])*(n-d[u])*edge[i].c;
dfs(v,dep+1);
}
}
}
void init_lca(){
dis[s]=0,ndis[s]=0,n2dis[s]=0;
dfs(s,1);
p[s][0]=s;
large=0;
while(1<<large<=n)large++;
large--;
for(int j=1;j<=large;j++)
for(int i=1;i<=n;i++)
p[i][j]=p[p[i][j-1]][j-1];
return ;
}
int find(int x){
if(f[x]!=x) f[x]=find(f[x]);
return f[x];
}
int lca(int x,int y){
if(d[x]>d[y])swap(x,y);
for(int i=large;i>=0;i--)
if(d[y]-d[x]>=1<<i) y=p[y][i];
if(x==y) return x;
for(int i=large;i>=0;i--)
if(p[x][i]!=p[y][i]){
x=p[x][i];
y=p[y][i];
}
return p[x][0];
}
int main(){
memset(head,-1,sizeof(head));
cin>>n>>m;
for(int i=1;i<=m;i++){
int d;
scanf("%d",&d);
if(d==1){
opt[i].k=d;
scanf("%d%d%d",&opt[i].x,&opt[i].y,&opt[i].w);
add_edge(opt[i].x,opt[i].y,opt[i].w);
add_edge(opt[i].y,opt[i].x,opt[i].w);
}
else{
opt[i].k=d;
scanf("%d%d",&opt[i].x,&opt[i].y);
}
}
init_lca();
for(int i=1;i<=n;i++)
f[i]=i;
for(int i=1;i<=m;i++){
if(opt[i].k==1){
f[find(opt[i].x)]=find(opt[i].y);
}
else{
if(find(opt[i].x)!=find(opt[i].y)){
printf("-1\n");
continue;
}
else{
long long dist,x=opt[i].x,y=opt[i].y;
int LCA=lca(x,y);
dist=d[x]+d[y]-(d[LCA]<<1);
long long sx,sy,sx2,sy2;
sx=ndis[x]-ndis[LCA]-(dis[x]-dis[LCA])*(n-d[x]);
sy=ndis[y]-ndis[LCA]-(dis[y]-dis[LCA])*(n-d[y]);
sx2=n2dis[x]-n2dis[LCA]-(dis[x]-dis[LCA])*(n-d[x])*(n-d[x])-(n-d[x])*(sx<<1);
sy2=n2dis[y]-n2dis[LCA]-(dis[y]-dis[LCA])*(n-d[y])*(n-d[y])-(n-d[y])*(sy<<1);
printf("%lld\n",(dist+1)*(sx+sy)-sx2-sy2);
}
}
}
return 0;
}
上一篇: iOS weak关键字实现原理
下一篇: Pairs Forming LCM
推荐阅读