[TIOJ] 1228. Phh多層次傳銷公司
題目連結:http://tioj.infor.org/problems/1228
本題是建中資訊校內複賽題,當時我在寫的時候完全不會線段樹甚麼的,所以我那時是直接照著做,然後稍微二分搜一下他的區間,就拿到了第二組subtask,因此比完之後我一直以為這題很簡單,直到聽完題解說要把樹壓扁、開BIT,我才發現原來沒有想像中的簡單。
--以上廢話--
本題把樹壓扁後就變成單點修改區間查詢的序列問題了,但什麼是把樹壓扁呢,在本題中可以發現我們會修改以及查詢的其實都是邊權,所以其實可以用一定的方法幫這些邊編號,而因為我們在查區間和時是用DFS的方法去跑,所以不妨就用DFS時碰到邊的順序幫它編號,但記得要開個mapping能讓它之後詢問跟修改時知道要對幾號做動作,大概就醬吧。
p.s本題記憶體有點卡,不能寫線段樹,只能寫BIT(至少我就醬被梗了一段時間
本題是建中資訊校內複賽題,當時我在寫的時候完全不會線段樹甚麼的,所以我那時是直接照著做,然後稍微二分搜一下他的區間,就拿到了第二組subtask,因此比完之後我一直以為這題很簡單,直到聽完題解說要把樹壓扁、開BIT,我才發現原來沒有想像中的簡單。
--以上廢話--
本題把樹壓扁後就變成單點修改區間查詢的序列問題了,但什麼是把樹壓扁呢,在本題中可以發現我們會修改以及查詢的其實都是邊權,所以其實可以用一定的方法幫這些邊編號,而因為我們在查區間和時是用DFS的方法去跑,所以不妨就用DFS時碰到邊的順序幫它編號,但記得要開個mapping能讓它之後詢問跟修改時知道要對幾號做動作,大概就醬吧。
p.s本題記憶體有點卡,不能寫線段樹,只能寫BIT(至少我就醬被梗了一段時間
#include <bits/stdc++.h>
using namespace std;
#define N 1000000
#define lowbit(x) ((x)&-(x))
struct node{
int child,val;
};
struct dian{
int l,r;
};
vector<node> tree[N+5];
dian dianMap[N+5];
int bianMap[N+5];
int BIT[N+5];
int n,q;
int counter=0;
int arr[N];
void foldTree(int);
void buildBIT();
void edit(int,int);
inline int sum(int);
int query(int,int);
int main(){
scanf("%d%d",&n,&q);
for(int i=0;i<n-1;i++){
int a,b,m;
scanf("%d%d%d",&a,&b,&m);
node tp;
tp.child=b;
tp.val=m;
tree[a].push_back(tp);
}
foldTree(0);
buildBIT();
for(int i=0;i<q;i++){
int type;
scanf("%d",&type);
if(type){
int w;
scanf("%d",&w);
int ans = query(dianMap[w].l, dianMap[w].r);
printf("%d\n",ans<<1);
}else{
int w,v;
scanf("%d%d",&w,&v);
edit(bianMap[w]+1,v-arr[bianMap[w]]);
arr[bianMap[w]] = v;
}
}
return 0;
}
void foldTree(int w){
dianMap[w].l=counter;
for(int i=0;i<tree[w].size();i++){
bianMap[tree[w][i].child]=counter;
arr[counter++]=tree[w][i].val;
foldTree(tree[w][i].child);
}
dianMap[w].r=counter;
}
void edit(int x,int d){
while(x<=n){
BIT[x]+=d;
x+=lowbit(x);
}
}
inline int sum(int x){
int ans=0;
while(x>0){
ans+=BIT[x];
x-=lowbit(x);
}
return ans;
}
int query(int l,int r){
return sum(r)-sum(l);
}
void buildBIT(){
for(int i=0;i<n;i++){
edit(i+1,arr[i]);
}
}
留言
張貼留言