NC14593. 喵喵的盆栽
描述
输入描述
第一行两个数字 n, q。表示模板的大小和问题的数量(n,q<=60000)
接下来n-1行表示(n-1)条双向边。
接下来q行
每行有三个数字 Ri Ai Bi(Ri,Ai,Bi<=n)。
输出描述
对于每个问题输出一行答案
示例1
输入:
5 3 1 2 1 3 2 4 2 5 1 2 3 3 5 4 3 3 5
输出:
1 2 1
C++14(g++5.4) 解法, 执行用时: 308ms, 内存消耗: 48200K, 提交时间: 2020-10-10 12:51:50
#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
#define int long long
const int N=1e6+5;
int n,m,top,xjh,t,head[N],dep[N],Ans[N],ru[N],chu[N],b[N],p[N],tree[N*4],lazy[N*4],sum[N*4],f[N][20];
struct node{
int len,id;
}a[N];
struct Node{
int a,b,id;
};
vector<Node>g[N];
struct E{
int too,next;
}edge[N*2];
//char buf[1<<21],*p1=buf,*p2=buf;
//inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
int ret=0,f=0;char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){ret=ret*10+c-48;c=gc();}
if(f)return -ret;return ret;
}
void add(int a,int b)
{
edge[++top].too=b;edge[top].next=head[a];head[a]=top;
}
bool pd(int x,int y)
{
if(ru[x]<=ru[y]&&chu[x]>=chu[y])return 1;
return 0;
}
int LCA(int x,int y)
{
if(pd(x,y))return x;
if(pd(y,x))return y;
int k=x;
for(int i=18;i>=0;i--)
if((f[k][i]>0)&&(!pd(f[k][i],y)))k=f[k][i];
return f[k][0];
}
int Dis(int x,int y)
{
int z=LCA(x,y);
return dep[x]+dep[y]-2*dep[z];
}
void dfs(int u,int fa)
{
ru[u]=++t;
f[u][0]=fa;dep[u]=dep[fa]+1;
int flag=0,ma=0;
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].too;
if(v==fa)continue;
flag=1;
dfs(v,u);
ma=max(ma,a[v].len);
}
chu[u]=++t;
if(!flag)
{
a[u]=(node){1,u};
return;
}
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].too;
if(v==fa)continue;
if(a[v].len==ma)
{
if(a[u].len==ma+1)a[u].id=u;
else{a[u].len=ma+1;a[u].id=a[v].id;}
}
}
}
void pushup(int nod)
{
tree[nod]=max(tree[nod*2],tree[nod*2+1]);
sum[nod]=0;
if(tree[nod]==tree[nod*2])sum[nod]+=sum[nod*2];
if(tree[nod]==tree[nod*2+1])sum[nod]+=sum[nod*2+1];
}
void pushdown(int nod)
{
tree[nod*2]+=lazy[nod];
tree[nod*2+1]+=lazy[nod];
lazy[nod*2]+=lazy[nod];
lazy[nod*2+1]+=lazy[nod];
lazy[nod]=0;
}
void change(int nod,int l,int r,int p,node x,int opt)
{
if(l==r)
{
if(opt==1)b[nod]=x.id;
if(opt==1)tree[nod]+=x.len;
else tree[nod]-=x.len;
sum[nod]=1;
return;
}
pushdown(nod);
int mid=(l+r)/2;
if(p<=mid)change(nod*2,l,mid,p,x,opt);
else change(nod*2+1,mid+1,r,p,x,opt);
pushup(nod);
}
void change2(int nod,int l,int r,int L,int R,int x)
{
if(l==L&&r==R)
{
tree[nod]+=x;
lazy[nod]+=x;
return;
}
pushdown(nod);
int mid=(l+r)/2;
if(R<=mid)change2(nod*2,l,mid,L,R,x);
else if(L>mid)change2(nod*2+1,mid+1,r,L,R,x);
else{
change2(nod*2,l,mid,L,mid,x);
change2(nod*2+1,mid+1,r,mid+1,R,x);
}
pushup(nod);
}
int query(int nod,int l,int r)
{
if(l==r)
{
xjh=b[nod];
return l;
}
pushdown(nod);
int mid=(l+r)/2;
if(tree[nod*2]==tree[nod])query(nod*2,l,mid);
else query(nod*2+1,mid+1,r);
}
bool cmp(int x,int y)
{
return dep[x]>dep[y];
}
int Jiao(int a,int b,int c,int d)
{
int p[10];
p[1]=LCA(a,c),p[2]=LCA(a,d),p[3]=LCA(b,c),p[4]=LCA(b,d);
sort(p+1,p+4+1,cmp);
int x=p[1],y=p[2];
return Dis(x,y);
}
void solve(int u,int fa,int L,int R)
{
node xu=(node){0,0};
if(fa)
{
change(1,1,n,L,a[fa],-1);
int ma=0;
for(int i=head[fa];i;i=edge[i].next)
{
int v=edge[i].too;
if(v==f[fa][0]||v==u)continue;
ma=max(ma,a[v].len);
}
for(int i=head[fa];i;i=edge[i].next)
{
int v=edge[i].too;
if(v==f[fa][0]||v==u)continue;
if(a[v].len==ma)
{
if(xu.len==ma+1)xu.id=fa;
else{xu.len=ma+1;xu.id=a[v].id;}
}
}
if(xu.len==0){xu.len=1;xu.id=fa;}
// if(u==4)cout<<"!!!"<<xu.len<<" "<<xu.id<<endl;
change(1,1,n,L,xu,1);
}
L--;p[L]=u;
change(1,1,n,L,a[u],1);
if(L<R)change2(1,1,n,L+1,R,1);
int wcy;
int pos=query(1,1,n);
// if(u==4)cout<<"##"<<xjh<<endl;
if(sum[1]==1)wcy=xjh;
else{
if(pos==L)wcy=u;
else wcy=p[pos];
}
for(int i=0;i<g[u].size();i++)
{
Node x=g[u][i];
Ans[x.id]=Dis(x.a,x.b);
// if(u==4)cout<<x.a<<" "<<x.b<<" "<<u<<" "<<wcy<<" "<<Ans[x.id]<<endl;
Ans[x.id]-=Jiao(x.a,x.b,u,wcy);
}
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].too;
if(v==fa)continue;
solve(v,u,L,R);
}
if(fa)
{
change(1,1,n,L+1,xu,-1);
change(1,1,n,L+1,a[fa],1);
}
change(1,1,n,L,a[u],-1);
if(L<R)change2(1,1,n,L+1,R,-1);
}
signed main()
{
n=read();m=read();
for(int i=1;i<n;i++)
{
int x=read(),y=read();
add(x,y);
add(y,x);
}
for(int i=1;i<=m;i++)
{
int x=read(),y=read(),z=read();
g[x].push_back((Node){y,z,i});
}
dfs(1,0);
for(int i=1;i<=18;i++)
for(int j=1;j<=n;j++)
f[j][i]=f[f[j][i-1]][i-1];
// cout<<a[2].len<<" "<<a[2].id<<endl;
// for(int i=1;i<=n;i++)cout<<i<<" "<<ru[i]<<" "<<chu[i]<<endl;
solve(1,0,n+1,n);
for(int i=1;i<=m;i++)printf("%lld\n",Ans[i]);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 171ms, 内存消耗: 11264K, 提交时间: 2019-06-05 17:45:16
#include <bits/stdc++.h>
using namespace std;
#define MAXNUM 66666
#define rep(i, s, t) for(int i=s;i<t;i++)
#define pii pair<int,int>
vector<int> e[MAXNUM];
pii maxf[MAXNUM];
int downpos[MAXNUM];
pii maxnum[MAXNUM][3];
int maxup[MAXNUM], tsize[MAXNUM], depth[MAXNUM], top[MAXNUM], fa[MAXNUM];
template<typename T> void up2(T x[], T num,int s=2)
{
rep(i, 0, s)if (num > x[i])swap(num, x[i]);
}
template<typename T> void up(T &x, T num)
{
if (num > x)x = num;
}
void dfs(int now, int p, int d)
{
depth[now] = d, tsize[now] = 1, fa[now] = p;
for (int k:e[now])
if (k != p)
{
up(maxf[k], {maxnum[now][0].first + 1, now});
dfs(k, now, d + 1), tsize[now] += tsize[k];
up2(maxnum[now], {maxnum[k][0].first + 1, k},3);
}
int maxnow = 0;
for (int i = e[now].size() - 1; i >= 0; i--)
if (e[now][i] != p)
{
int k = e[now][i];
up(maxf[k], {maxnow + 1, now});
maxnow = max(maxnow, maxnum[k][0].first + 1);
}
if (maxnum[now][0].first == maxnum[now][1].first)
downpos[now] = now;
else downpos[now] = downpos[maxnum[now][0].second];
}
void dfstop(int now, int p, int nowt)
{
top[now] = nowt;
int maxpos = 0;
for (int k:e[now])if (k != p && tsize[k] > tsize[maxpos])maxpos = k;
if (maxpos)dfstop(maxpos, now, nowt);
for (int k:e[now])if (k != p && k != maxpos)dfstop(k, now, k);
}
int lca(int a, int b)
{
while (top[a] != top[b])
{
if (depth[top[a]] < depth[top[b]])swap(a, b);
a = fa[top[a]];
}
if (depth[a] < depth[b])swap(a, b);
return b;
}
int jiao(int a[2], int b[2])
{
pii tmp[2] = {{0, 0}, {0, 0}};
rep(i, 0, 2)
rep(j, 0, 2)
{
int k = lca(a[i], b[j]);
up2(tmp, {depth[k], k});
}
int x = lca(tmp[0].second, tmp[1].second);
return depth[tmp[0].second] + depth[tmp[1].second] - 2 * depth[x];
}
int maxall[MAXNUM];
void dfs2(int now, int p)
{
if(p)up(maxf[now], {maxf[p].first + 1, p});
for (int k:e[now])
if (k != p)
{
pii tmp[2] = {maxf[now], {0, 0}};
rep(i, 0, 3)if (maxnum[now][i].second != k)up2(tmp, maxnum[now][i]);
if (tmp[0].first == tmp[1].first)maxup[now] = now;
else if (tmp[0].second != p)maxup[now] = downpos[tmp[0].second];
else maxup[now] = maxup[p];
dfs2(k, now);
}
up2(maxnum[now], maxf[now],3);
if (maxnum[now][0].first == maxnum[now][1].first)maxall[now] = now;
else if (maxnum[now][0].second != p)maxall[now] = downpos[maxnum[now][0].second];
else maxall[now] = maxup[p];
}
int main()
{
int n, q, a, b, c;
scanf("%d%d", &n, &q);
rep(i, 1, n)scanf("%d%d", &a, &b), e[a].push_back(b), e[b].push_back(a);
dfs(1, 0, 0);dfs2(1, 0);dfstop(1, 1, 1);
while (q--)
{
scanf("%d%d%d", &a, &b, &c);
int k1[2] = {b, c}, k2[2] = {a, maxall[a]};
int xx = lca(b, c);
printf("%d\n", depth[b] + depth[c] - 2 * depth[xx] - jiao(k1, k2));
}
}