누 드 체인 으로 나 뉘 어 데이터 가 좀 큰 것 같 습 니 다.선분 트 리 로 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;
}
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전
Udemy 에서 공부 한 것을 중얼거린다
Chapter3【Integer Reversal】
(예)
문자열로 숫자를 반전 (toString, split, reverse, join)
인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.