[SPOJ QTREE] 트 리 체인 분할 템 플 릿

3857 단어 데이터 구조
선분 트 리 로 구 해 보 세 요. 경로 의 최대 치 를 구 했 기 때문에 디 테 일 에 주의 하 세 요.
#include
#include
#include
using namespace std;
const int MAXN = 10010;
#define lson (pos<<1)
#define rson (pos<<1|1)
const int INF = (1 << 30);
int n;
//--------------------------------------------------
struct Edge{
    int to,next;
}edge[MAXN * 2];
int head[MAXN],tot;
int top[MAXN];
int fa[MAXN];
int deep[MAXN];
int num[MAXN];
int p[MAXN];
int fp[MAXN];
int son[MAXN];
int pos;
void init(){
    tot = 0;
    memset(head,-1,sizeof(head));
    pos = 1;
    memset(son,-1,sizeof(son));
}
void addedge(int u,int v){
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot ++;
}
void dfs1(int u,int pre,int d){
    deep[u] = d;
    fa[u] = pre;
    num[u] = 1;
    for(int i = head[u]; i != -1; i = edge[i].next){
        int v = edge[i].to;
        if(v != pre){
            dfs1(v,u,d + 1);
            num[u] += num[v];
            if(son[u] == -1 || num[v] > num[son[u]])
                son[u] = v; //    
        }
    }
}
void getpos(int u,int sp){
    top[u] = sp;
    p[u] = pos++;
    //printf("%d %d
",u,p[u]); fp[p[u]] = u; if(son[u] == -1) return; getpos(son[u],sp); for(int i = head[u]; i != -1; i = edge[i].next){ int v = edge[i].to; if(v != son[u] && v!= fa[u]) getpos(v,v); } } //---------------------------------------------- int maxv[MAXN << 2]; // void build(){ memset(maxv,0,sizeof(maxv)); } void pushup(int pos){ maxv[pos] = max(maxv[lson],maxv[rson]); } void update(int l,int r,int to,int value,int pos){ if(l == r){ maxv[pos] = value; return; } int mid = (l + r) >> 1; if(to <= mid) update(l,mid,to,value,lson); else update(mid + 1,r,to,value,rson); pushup(pos); } int query(int l,int r,int L,int R,int pos){ if(L <= l && r <= R) return maxv[pos]; int mid = (l + r) >> 1; int ret = - INF; if(L <= mid) ret = max(ret,query(l,mid,L,R,lson)); if(R > mid) ret = max(ret,query(mid + 1,r,L,R,rson)); return ret; } //------------------------------------------------------- int find(int u,int v){ int f1 = top[u],f2 = top[v]; int tmp = 0; while(f1 != f2){ if(deep[f1] < deep[f2]){ swap(f1,f2); swap(u,v); } tmp = max(tmp,query(1,pos,p[f1],p[u],1)); u = fa[f1]; f1 = top[u]; } if(u == v) return tmp; if(deep[u] > deep[v]) swap(u,v); return max(tmp,query(1,pos,p[son[u]],p[v],1)); } //---------------------------------------------------------- struct E{ int from,to,value; }e[MAXN]; int main(){ int T; int u,v; scanf("%d",&T); while(T--){ scanf("%d",&n); init(); for(int i = 0; i < n - 1; i++){ scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].value); addedge(e[i].from,e[i].to); addedge(e[i].to,e[i].from); } dfs1(1,0,0); getpos(1,1); build(); for(int i = 0; i < n - 1; i++){ if(deep[e[i].from] > deep[e[i].to]) swap(e[i].from,e[i].to); // , update(1,pos,p[e[i].to],e[i].value,1); } char op[10]; while(scanf("%s",op) != EOF){ if(op[0] == 'D') break; scanf("%d%d",&u,&v); if(op[0] == 'Q'){ printf("%d
",find(u,v)); } else{ update(1,pos,p[e[u - 1].to],v,1); } } if(T) puts(""); } return 0; }

좋은 웹페이지 즐겨찾기