CF1844G Tree Weights

智慧的 Ad-hoc。

Ad-hoc 只能乱想，还是胡一下如何思考。

考虑给出相邻编号节点的距离 $dis(i,i+1)$ 的意义何在。一个想法是尝试递推。设 $u_i=\operatorname{LCA}(i,i+1)$，但是具体如何？比较智慧的是考虑 $dis(i,i+1)=d_i+d_{i+1}-2\cdot d_{u_i}$。直接对原式模二以去掉 $2\cdot d_{u_i}$ 项，式子变为 $dis(i,i+1)=d_i+d_{i+1}\pmod 2$，我们容易递推出 $d_{i+1}\pmod 2$。继续智慧，尝试继续采用类似的思路，利用 $d_i\pmod 2$ 的信息，利用 $dis(i,i+1)=d_i+d_{i+1}-2\cdot d_{u_i}\pmod 4$ 继续递推即可，重复该过程 $\log_2 V$ 次即可。时间复杂度为 $\mathcal O(n(\log n+\log V))$。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long 
using namespace std;
const int N=1e5+10,M=18,K=60;
template<class T>
inline void read(T &x)
{
    x=0;bool d=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')d=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(d)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n;
int u[N],v[N];
int tot,head[N],ver[N<<1],ne[N<<1];
int dep[N],fa[N][M+5],lca[N];
ll dis[N],d[N],g[N];

inline void add(int u,int v)
{
    ver[++tot]=v;
    ne[tot]=head[u];
    head[u]=tot;
}
void dfs(int x)
{
    dep[x]=dep[fa[x][0]]+1;
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(y==fa[x][0])continue;
        fa[y][0]=x;
        for(int j=1;j<=M;j++)fa[y][j]=fa[fa[y][j-1]][j-1];
        dfs(y);
    }
}
inline int LCA(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y);
    for(int i=M;~i;i--)
        if(dep[fa[x][i]]>=dep[y])
            x=fa[x][i];
    if(x==y)return x;
    for(int i=M;~i;i--)
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
int main()
{
    read(n);
    for(int i=2;i<=n;i++)read(u[i],v[i]),add(u[i],v[i]),add(v[i],u[i]);
    for(int i=2;i<=n;i++)read(dis[i]);
    dfs(1);
    for(int i=2;i<=n;i++)lca[i]=LCA(i-1,i);
    for(int t=1;t<=K;t++)
    {
        ll all=(1ll<<t)-1;
        for(int i=2;i<=n;i++)
            d[i]=((dis[i]&all)+(d[lca[i]]<<1)-d[i-1])&all;
    }
    for(int i=2;i<=n;i++)
        if(d[i]<=d[fa[i][0]])return puts("-1"),0;
    for(int i=2;i<=n;i++)
        if(d[i-1]+d[i]-(d[lca[i]]<<1)!=dis[i])return puts("-1"),0;
    for(int i=2;i<=n;i++)
        printf("%lld\n",abs(d[u[i]]-d[v[i]]));
    return 0;
}