AES多层加密逆向
2026/7/2 3:17:08
思路
首先，kiki 可以从父节点递推得到，ki=kfi+aiki=kfi+ai。其中 aiai 为以节点 ii 结尾的合法括号序列数量。因此只要求出每个节点的 aa。
经典技巧，将 (( 的权值设为 11，)) 设为 −1−1 ，做树上前缀和。设点 uu 的前缀和为 sumusumu。则以 uu 结尾的合法括号子串的开头 vv 必须满足：
- sumfv=sumusumfv=sumu。
- 对于 v→uv→u 这条链上的所有点 xx，有 sumx≥sumusumx≥sumu。
在 DFS 过程中开一棵值域线段树维护 1→u1→u 这条链上每个 sumsum 值对应的最大节点深度。这样就能找到 sump<sumusump<sumu 且深度最大的节点 pp。
设 ask(x,y)ask(x,y) 表示 1→x1→x 链上 sum=ysum=y 的节点数量。则 au=ask(fu,k)−ask(p,k)au=ask(fu,k)−ask(p,k)。
第一遍 DFS 求出所有询问并离线下来。
第二遍 DFS 求出所有点的 aa。
第三遍 DFS 对 aa 做树上前缀和得到所有点的 kk 即可。
时间复杂度 O(nlogn)O(nlogn)。
Code
#include <bits/stdc++.h> |
#define rept(i,a,b) for(int i(a);i<=b;++i) |
#define ls(p) ((p)<<1) |
#define rs(p) ((p)<<1|1) |
#define eb emplace_back |
#define int long long |
using namespace std; |
constexpr int N=5e5+5; |
struct Query{ |
int k,coef,id; |
// k：目标值 |
// coef：贡献系数，1/-1 |
// id：贡献给到的节点 |
Query(int _k,int _coef,int _id):k(_k),coef(_coef),id(_id){} |
}; |
struct SegTree{ |
int t[N<<3]; |
void update(int p,int pl,int pr,int pos,int x){ // 单点修改 |
if(pl==pr) return void(t[p]=x); |
int mid=pl+pr>>1; |
if(pos<=mid) update(ls(p),pl,mid,pos,x); |
else update(rs(p),mid+1,pr,pos,x); |
t[p]=max(t[ls(p)],t[rs(p)]); |
} |
int query(int p,int pl,int pr,int l,int r){ // 区间max |
if(l>r) return 0; |
if(l<=pl&&pr<=r) return t[p]; |
int mid=pl+pr>>1,a=0; |
if(l<=mid) a=max(a,query(ls(p),pl,mid,l,r)); |
if(mid<r) a=max(a,query(rs(p),mid+1,pr,l,r)); |
return a; |
} |
}sgt; |
char s[N]; |
int sum[N],dep[N],cnt[N<<1],a[N],st[N]; |
int n,m,ans; |
vector<int> g[N]; |
vector<Query> q[N]; |
void dfs1(int u){ |
int lst=sgt.query(1,1,m,sum[u],sum[u]); |
sgt.update(1,1,m,sum[u],dep[u]); |
st[dep[u]]=u; |
for(int v:g[u]){ |
sum[v]=sum[u]+(s[v]=='('?1:-1); |
dep[v]=dep[u]+1; |
if(s[v]==')'){ |
int bound=sgt.query(1,1,m,1,sum[v]-1); |
q[u].eb(sum[v],1,v); |
if(bound) q[st[bound]].eb(sum[v],-1,v); |
} |
dfs1(v); |
} |
sgt.update(1,1,m,sum[u],lst); |
} |
void dfs2(int u){ |
++cnt[sum[u]]; |
for(Query x:q[u]){ |
a[x.id]+=x.coef*cnt[x.k]; |
} |
for(int v:g[u]) dfs2(v); |
--cnt[sum[u]]; |
} |
void dfs3(int u){ |
for(int v:g[u]){ |
a[v]+=a[u]; |
dfs3(v); |
} |
ans^=u*a[u]; |
} |
signed main(){ |
cin.tie(0)->sync_with_stdio(0); |
cin>>n>>s+1; |
m=n<<1; |
rept(i,2,n){ |
int x;cin>>x; |
g[x].eb(i); |
} |
g[0].eb(1); |
sum[0]=n,dep[0]=1; // 为了不出负数，sum统一加上n |
dfs1(0),dfs2(0),dfs3(0); |
cout<<ans; |
return 0; |
} |
分类: 题解