题目大意:
从根节点1走到某个节点J, 会有路径X1, X2, X3, X4, .......XK, 问是否存在H <= K, 使得X1,X2....XH的路径以Bi为边权的总权值小于路径X1, X2, ... XK以Ai为边权的总权值。若存在,打出根节点1到XH的长度,否则,打印0
分析:
首先DFS求出根节点1到各个节点的长度以及A, B 两类边权的总权值,在通过倍增数组pre[i][j]向上来查找目标节点
//AC CODE:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 2e5 + 10;
const ll root = 1;
const ll inc = 1;
const ll floors = 30;
struct node{
ll to;
ll wa;
ll wb;
}ty;
vector<struct node>ver[maxn];
ll keya[maxn];
ll keyb[maxn];
ll len[maxn];
ll pre[maxn][floors];
int vis[maxn];
void dfs(ll s){
vis[s] = 1;
for(int i = 0; i < ver[s].size(); i++){
ll aim = ver[s][i].to;
if(vis[aim] == 0){
keya[aim] = keya[s] + ver[s][i].wa;
keyb[aim] = keyb[s] + ver[s][i].wb;
len[aim] = len[s] + inc;
pre[aim][0] = s;
dfs(aim);
}
}
return;
}
void init(ll n){
fill(keya, keya + n + 1, 0);
fill(keyb, keyb + n + 1, 0);
fill(len, len + n + 1, 0);
fill(vis, vis + n + 1, 0);
for(ll i = 0; i <= n; i++){
ver[i].clear();
pre[i][0] = i;
}
}
void addlen(ll n){
for(ll i = 1; i < floors; i++){
for(ll j = 1; j <= n; j++){
pre[j][i] = pre[pre[j][i - 1]][i - 1];
}
}
}
int main(){
int t;
cin>>t;
while(t--){
ll n;
ll p, a, b;
cin>>n;
init(n);
for(ll i = 2; i <= n; i++){
scanf("%lld%lld%lld", &p, &a, &b);
ty.to = i;
ty.wa = a;
ty.wb = b;
ver[p].push_back(ty);
ty.to = p;
ver[i].push_back(ty);
}
dfs(root);
addlen(n);
for(ll i = 2; i <= n; i++){
ll cp = keya[i];
ll current = i;
while(cp < keyb[current]){
ll j;
for(j = floors - 1; j >= 0; j--){
ll num = pre[current][j];
if(cp < keyb[num]){
current = num;
break;
}
}
if(j == -1) current = pre[current][0];
//cout<<current<<" ";
}//cout<<endl;
//printf("%lld ", current);
printf("%lld ", len[current]);
}printf("\n");
}
return 0;
}