HDU 5044 - tree - 트 리 체인 분할 + 트 리 배열

누 드 체인 으로 나 뉘 어 데이터 가 좀 큰 것 같 습 니 다.선분 트 리 로 T 를 유지 하고 읽 기 마 우 스 를 추가 하면 트 리 배열 이 지나 갈 수 있 습 니 다....................................................
나무 모양 배열 도 필요 없 을 것 같 습 니 다.그냥 배열 로 해도 되 는데...

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define BUF_SIZE 100000

bool IOerror=0;
inline bool blank(char ch)
{
    return ch==' '||ch=='
'||ch=='\r'||ch=='\t'; } inline char nc() { static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE; if (p1==pend) { p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin); if (pend==p1) { IOerror=1; return -1; } //{printf("IO error!
");system("pause");for (;;);exit(0);} } return *p1++; } inline void read(int &x) { bool sign=0; char ch=nc(); x=0; for (; blank(ch); ch=nc()); if (IOerror)return; if (ch=='-')sign=1,ch=nc(); for (; ch>='0'&&ch<='9'; ch=nc())x=x*10+ch-'0'; if (sign)x=-x; } inline void read(char *s) { char ch=nc(); for (; blank(ch); ch=nc()); if (IOerror)return; for (; !blank(ch)&&!IOerror; ch=nc())*s++=ch; *s=0; } /// typedef long long ll; const int MAXN = 100000+50; int n,m; ll ans [MAXN]; int edge_id[MAXN]; struct Edge { int to,next; } edge[MAXN*2]; int head[MAXN],tot; int top[MAXN];//top[v] v int fa[MAXN]; // int deep[MAXN];// int num[MAXN];//num[v] v int p[MAXN];//p[v] v int fp[MAXN];// p int son[MAXN];// int pos; int out[MAXN];//dfs void init() { tot = 0; memset(head,-1,sizeof(head)); pos = 0; 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) // dfs fa,deep,num,son { 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) // dfs top p { top[u] = sp; p[u] = ++pos; fp[p[u]] = u; if(son[u]!=-1) 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); } out[u]=pos; } struct TREE { ll tree[MAXN+5]; void init() { memset(tree,0,sizeof tree); } int lowbit(int x) { return x&-x; } void add(int x,int value) { for (int i=x; i<=n; i=i+lowbit(i)) { tree[i]+=value; } } ll get(int x) { ll sum=0; for (int i=x; i; i-=lowbit(i)) { sum+=tree[i]; } return sum; } void update_point(int u,int v,int z)// u->v sum { int f1=top[u],f2=top[v]; while(f1!=f2) { if (deep[f1]deep[v] ) swap(u,v); // update(1,1,pos,p[u],p[v],z); // val(u) u fu , son[u] add(p[u],z); add(p[v]+1,-z); } void update_edge(int u,int v,int z)// u->v sum { int f1=top[u],f2=top[v]; ll tmp=0; while(f1!=f2) { if (deep[f1]deep[v] ) swap(u,v); if (p[son[u]]>p[v]) return ; // update(1,1,pos,p[son[u]],p[v],z); // val(u) u fu , son[u] add(p[son[u]],z); add(p[v]+1,-z); } void get_ans( ) { for (int i=1;i<=n;i++) ans[fp[i]]=get(i); } void get_ans_edge() { for (int i=1;i<=n;i++) { int x=fp[i]; int id=edge_id[x]; ans[id]=get(i); } } }; TREE tp; struct node { int x,y,z; node () {} node(int a,int b,int c) { x=a,y=b,z=c; } }; vector a1; vector a2; int uu[MAXN]; int vv[MAXN]; int main() { // freopen("in.txt","r",stdin); int cnt=1; int t; //cin>>t; read(t); while(t--) { a1.clear(); a2.clear(); init(); // scanf("%d%d",&n,&m); read(n); read(m); int u,v; for (int i=1; i1) printf(" "); printf("%lld",ans[i]); } printf("
"); tp.init(); for (int i=0; i1) printf(" "); printf("%lld",ans[i]); } printf("
"); } return 0; }

좋은 웹페이지 즐겨찾기